search
Log In

Recent questions tagged asymptotic-notations

0 votes
0 answers
1
I didn't understand Big-O notation: This is CORMEN exercise problem - 3.1-2 Solution link: https://www.csee.umbc.edu/~nam1/TA/HWSols/hw1sol.pdf
asked Jul 23, 2018 in Algorithms Swapnil Naik 157 views
0 votes
1 answer
2
1 vote
1 answer
3
which of the following estimates are true? Explain with valid reasons. a) (2n)! is theta (n)! b) log((2n)!) is theta (log(n)!)
asked Jul 14, 2018 in Algorithms AIkiran01 835 views
1 vote
0 answers
4
What is the time complexity of the below code? for($k=n^{10};k \geq 5;k=k^{\frac{1}{7}},k=k^2$) { $k=k^5;$ $k=k-10$ } My answer comes to be $O(log_{\frac{7}{10}}log_5(n^{10}))$ Please verify.
asked Jul 14, 2018 in Algorithms Ayush Upadhyaya 252 views
4 votes
0 answers
5
for(int i=0; i < n; i++) { for(int j=0; j < (2*i); j+=(i/2)) { cout<<"Hello Geeks"; } } is it o(nlogn)??
asked Jul 10, 2018 in Algorithms vijju532 672 views
2 votes
2 answers
6
For the below code : foo() { for(i=1;i<=n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) c++; } } } Here k is executing j-1 times and j is executing i times and i is executing n^2 times , so first I am doing summation from k=0 to k=j-1 over k ... 1 to n^2 , I am getting order of n^8 .But this is getting too large , I checked with an example , it is not matching ,So please correct where I went wrong .
asked Jun 28, 2018 in Algorithms radha gogia 362 views
1 vote
1 answer
7
Consider the following functions
asked Jun 28, 2018 in Algorithms Doley 70 views
0 votes
1 answer
8
n2 + O(n2) = Theta(n2) I am not getting how can we say that tightest bound is in terms of theta , because theta(n2 ) implicitly implies Big-Omega(n2 ) and Big O(n2 ) , Now If we say the function f(n) is Big-Omega(n2 ) , then f(n) can be any of the ... but on LHS , we will never get a function greater than n2 so how can we say the tightest bound to be Big-Omega(n2 ) ? Please explain briefly .
asked Jun 24, 2018 in Algorithms radha gogia 226 views
0 votes
0 answers
9
$T\left ( n,c \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( c,n \right )=\Theta \left ( n \right )$ for $c\leq 2$ $T\left ( n,n \right )=\Theta \left ( n \right )+T\left ( n,\frac{n}{2} \right )$ How to find complexity for this recurrence relation?
asked Jun 22, 2018 in Algorithms srestha 148 views
1 vote
0 answers
10
What will be the time complexity of the following algorithm ? A(n){ if(n<=1) return 1; for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } } }
asked Jun 17, 2018 in Algorithms kartikeya2812 182 views
2 votes
1 answer
11
Can Extended Masters theorem be applied to the following recursive equation ? $T(n)=n^{1/2}T(n^{1/2})+n$ I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ I was wondering if this equation could be solved using masters theorem, like the way Tauhin Gangwar has solved here - https://gateoverflow.in/60532/find-tc-t-n-2t-n-1-2-1
asked Jun 11, 2018 in Algorithms Hardik Maheshwari 1.4k views
0 votes
0 answers
12
Indicate for pair of expressions (A,B) whether A is O, o, Ω, ω or of B? A = lg(n!) B = lg(n^n)
asked Jun 11, 2018 in Algorithms Aarvi Chawla 63 views
1 vote
2 answers
13
0 votes
0 answers
14
#DAA Prove that if: f(n) = amnm + am-1nm-1 + am-2nm-2 + am-3nm-3 + .........+ a1n + a0 then f(n) = O(nm) .
asked Jun 6, 2018 in Algorithms Naveen Kumar 3 65 views
1 vote
2 answers
15
Which of the following statements is/are valid? 1. Time Complexity of QuickSort is Θ(n^2) 2. Time Complexity of QuickSort is O(n^2) 3. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). 4. Time complexity of all computer algorithms can be written as Ω(1)
asked Jun 6, 2018 in Algorithms jatinkumar 970 views
0 votes
1 answer
16
0 votes
1 answer
17
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) =T(an)+T((1-a)n)+cn, where a is constant in the range 0<a<1 and c>0 is also a constant.
asked Apr 27, 2018 in Algorithms Neha_16 450 views
0 votes
1 answer
18
Big Omega question : 5n+3>=C2n for which value of c and n condition satisfies?
asked Apr 17, 2018 in Algorithms once_2019 73 views
0 votes
1 answer
19
Compute: T(n) = 2^nT(n/2) +n^n 1)theta(n^n) 2)theta(nlogn) 3)theta(n^nlogn) 4)none of these.
asked Apr 15, 2018 in Algorithms Harshit Pandey 202 views
2 votes
2 answers
21
0 votes
0 answers
22
When T(n) = a T(n/b) + f(n) If on solving we get g(n) as upper bound solution for the recurrence. Is f(n) = O( g(n) ) always correct?
asked Apr 3, 2018 in Algorithms smsubham 140 views
1 vote
1 answer
23
Find the solution of recurrence $T(n) = 4T(\frac{n}{2}) + n^{2}$ by substitution method.
asked Apr 2, 2018 in Algorithms Mk Utkarsh 240 views
2 votes
1 answer
24
Use the recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n-1)+T($\frac{n}{2}$)+n. Use substitution method to verify the answer.
asked Mar 9, 2018 in Algorithms Tesla! 480 views
1 vote
1 answer
25
For a given constant c $\in \mathbb{R}$, we define the iterated function $f_{c}^{*}$ by $f_{c}^{*}$(n)=min{${i\geq 0: f^{(i)}(n)<c}$} For each of the following function f(n) and constants c, give as tight a bound as possible on $f_{c}^{*}$ f(n) c $f_{c}^{*}$(n) $\sqrt{n}$ 2 $\sqrt{n}$ 1 n/lg n 2
asked Mar 7, 2018 in Algorithms Tesla! 165 views
1 vote
2 answers
26
2 votes
1 answer
27
Given f(n) = ω(n2). Which of the following can never hold? a. f(n) = O (n3) b. f(n) = Ω (n2) c. f(n) = θ (n2) d. f(n) = ω (n)
asked Jan 30, 2018 in Algorithms Tuhin Dutta 208 views
2 votes
1 answer
28
plz help me . how to solve that type of question
asked Jan 27, 2018 in Algorithms 92komal 162 views
3 votes
1 answer
29
time complexity questions like : h(n)=O(n2); f(n)= O(logn); g(n)=omega(n2); what is the complexity of :::: 1. h(n)-g(n)=?? 2. h(n)-f(n)=??? elaborate plz
asked Jan 22, 2018 in Algorithms akankshadewangan24 198 views
2 votes
0 answers
30
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ?
asked Jan 22, 2018 in Algorithms ashish pal 246 views
...