retagged by
490 views

1 Answer

0 votes
0 votes

T(n) = T(sqrt n) +1

let n = 2m                   .........................(1)

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

assume T(2m) = S(m)

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

apply master theorem

S(m) = theeta (log m)

from (1)

so T(n) = theeta (log log n) 

Related questions

3 votes
3 votes
1 answer
2
3 votes
3 votes
1 answer
3
im.raj asked Jun 16, 2016
2,952 views
A. T(n) = $O( n Log n)$B. T(n) = $O({(logn)}^2)$C. T(n) = $O(n)$D. T(n) = $O(n^2)$
6 votes
6 votes
2 answers
4
$ourav asked May 20, 2016
13,767 views
Consider the recurrence relation T(n) = T(n-1) + T(n/2) + nWhich of the following is a good tight upper bound on T(n)(a) $\Theta (n^{2})$(b) $\Theta (n^{2}\log n)$(c) $\T...