retagged by
3,253 views
4 votes
4 votes

Which of the following represents most appropriate asymptotic solution for given reccurance:

(A) O(n)

(B) O(log n)

(C) O(log log n)

(D) O(log n)2

retagged by

1 Answer

0 votes
0 votes

T(n) = T( √n) + log2 n   _____________    Eqn 1

Let's take n = 2m , taking log both side.

log2 n = m log22 put in Eqn 1.

T(2m) = T(2m/2) + log2 2m _____________ Eqn 2   

[ ∵ logb bn = n ] using this we can rewrite Eqn 2 as :

T(2m) = T(2m/2) + m

or

S(m) = S(m/2) +m

solve using MT we get, S(m) = O(m)

change the value of m to log2n.

so TC is log2n

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
Saurav asked Aug 31, 2015
973 views
The number of leaf nodes in the recurrence tree of the recurenceT(n) = T(n/4) + T(n/2) + n^2
1 votes
1 votes
0 answers
3
Ravi prakash pandey asked Aug 1, 2017
175 views
Generally a recurrence relation is given asT(n)=aT(n/b)+ f(n)where a is no of sub prblm of size n/b each.Can there be any real scenario where a>b.I mean if n is divided i...
1 votes
1 votes
1 answer
4