patternMinor
Recurrence and Time complexity
Viewed 0 times
andcomplexityrecurrencetime
Problem
I am having problem solving this recurrence. Can anyone help me with this please:
$$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$
$$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$
Solution
Let $S(m) = \log_2 (2T(2^m))$. Then $S(m)$ satisfies the recurrence
$$
S(m) = 2S(m-1), \quad S(0) = 3.
$$
You can work it out from here.
$$
S(m) = 2S(m-1), \quad S(0) = 3.
$$
You can work it out from here.
Context
StackExchange Computer Science Q#143804, answer score: 2
Revisions (0)
No revisions yet.