Reccurrence T(n) = T(n^(1/2)) + 1
Solution 1
hint: assume n = 22m or m = log2log2n, and you know 22m-1 * 22m-1 = 22m so, if you define S(m)=T(n) your S will be:
S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m)=T(n) = Θ(log2log2n)
extend it for the general case.
In recursion like T(n) = T(n/2) + 1, in each iteration, we reduce the height of the tree to half. This leads to Θ(logn). In this case, however, we divide the input number by a power of two (not by two) so it turns out to be Θ(log log n ).
Solution 2
Here is how you can find the answer without any hints, just by using math.
Start unrolling the recursion: .
The recursion will at some point stop, so we have to find a reasonable stopping point. Trying 0, 1, 2, you can see that 2 looks good, because you can easily solve the equation: .
So the recursion will continue log(log(n))
times and this is your time complexity.
P.S. a little bit harder recurrence was solved here.
ftsk33
Updated on July 09, 2022Comments
-
ftsk33 almost 2 years
I've been looking at this reccurrence and wanted to check if I was taking the right approach.
T(n) = T(n^(1/2)) + 1 = T(n^(1/4)) + 1 + 1 = T(n^(1/8)) + 1 + 1 + 1 ... = 1 + 1 + 1 + ... + 1 (a total of rad n times) = n^(1/2)
So the answer would come to theta bound of n^(1/2)
-
ftsk33 about 12 yearsso this means the the height of the recurrence tree is log log n?
-
Saeed Amiri about 12 yearsYes exactly it is log log n (in base 2), in fact sqrt reduces value in power of 2 ( not two times).
-
Soner from The Ottoman Empire over 5 yearsI like to study with your answers, I hope a day I will reach >10k points thereby working with you, sir. +1
-
Soner from The Ottoman Empire over 5 yearsFor those having difficulty to catch loglogn part, the image can help you.
-
Rafay about 5 years@snr Thanks for providing the handout. Cheers!