GATE CSE
First time here? Checkout the FAQ!
x
0 votes
121 views

Can you please find time complexity of the recurrence using Variable Substitue method and Master Theroem:

What is the time complexity of the following recursive function 
int recursion (int n) 

if(n ≤ 1) 
return 1; 
else 
return(recursion(sqrt(n)) + 1); 
}

 

// i solved it using substitution method.

asked in Algorithms by Veteran (14.7k points)  
edited by | 121 views

1 Answer

+2 votes
Best answer


T(n) = T(root(n))+1
let n= 2k
T(2^k)=T(2(k/2))+1
let T(2K) = G(k)
G(k) = G(k/2)+1
using extended master's theorem
a=1 b=2 k=0,p=0
a=bk it will be G(k) = O(logk) = T(2k)
we know K=logn substitute in O(logk) = O(loglogn)

Credits: Sanju

answered by Veteran (14.7k points)  
edited by

Related questions

0 votes
3 answers
2
0 votes
2 answers
3
asked in Algorithms by rahuldb Junior (955 points)   | 70 views


Top Users Jul 2017
  1. Bikram

    3960 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1848 Points

  4. joshi_nitish

    1654 Points

  5. Arjun

    1290 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1100 Points

  8. Shubhanshu

    1052 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    702 Points


24,018 questions
30,955 answers
70,327 comments
29,337 users