GATE CSE
First time here? Checkout the FAQ!
x
0 votes
90 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.4k points)  
edited by | 90 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.4k points)  
edited by

Related questions

0 votes
0 answers
2
+1 vote
1 answer
3
asked in Algorithms by harshit agarwal (379 points)   | 59 views
Top Users Feb 2017
  1. Arjun

    5224 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. Debashish Deka

    2356 Points

  6. sriv_shubham

    2298 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. sh!va

    1654 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,832 questions
25,986 answers
59,623 comments
22,042 users