edited by
1,314 views
0 votes
0 votes

I got this question from here https://gateoverflow.in/169286/time-complexity

Is this Question Correct i have doubt . If correct please explain

Which of the following statements is/are TRUE? 
$i)$ The time complexity of recurrence relation $A(n) = 3A(n/2)+n^{2} $is asymptotically faster than $T(n) = 4T(n/2)+ n^{2}$ 

$ii)$ The time complexity of recurrence relation $A(n) = 512 A(n/2) + O(n^{50})$ is asymptotically faster than $T(n) = 7T(n-53) + O(1)$, $T(0) = 1$.

i am getting till here

$I)O(n^{2}) < O( n^{2}log n)$  so $O( n^{2} log n)$ is asymptotically faster

$II)O( 7 ^ {n/53}) > O(n ^{50})$ so $O( 7 ^ {n/53})$ is asymptotically faster

But i am not able to get the answer because of question statement .

 

edited by

Please log in or register to answer this question.

Related questions

492
views
0 answers
0 votes
garvit_vijai asked Nov 17, 2018
492 views
How to solve the following recurrence relation?T(n) = T(n-6) + n2 , n>7T(n) = 1 , n<= 7
964
views
1 answers
1 votes
aditi19 asked Oct 27, 2018
964 views
how to compute time complexity of this kind of recurrence relation-T(n)=T(n/2)+T(n/4)+T(n/8)+n
1.5k
views
1 answers
2 votes
Manu Thakur asked Aug 18, 2017
1,548 views
Can you please solve this following question further?What will be the time complexity?
684
views
2 answers
2 votes
A_i_$_h asked Oct 16, 2017
684 views
A) T(n) = 2T(root(n)) + 1 ; n>2 T(n) =1 ; 0 < n <= 2B) f(n) =ng(n) = n(1+sin n)where n is positive integerwhich is true?1.f(n) = O(g(n))2.f(n) = $\Omega$(g(n))