Runtime of Recurrence relation

Question

Just had this on a quiz: T(n) = 4T(sqrt(n)) + 5

I simplified it using substitution and got F(k) = 4F(k/2) + 5

Using the master theorem I guessed it was O(logn). Is this accurate?

Answer 1

Define

F(n) = T(2^n)

Then we have that

F(n) = 4F(n/2) + 5

By the master theorem, we have that

a = 4
b = 2
f(n) = 5 = O(1) = O(m^0), so c = 0
0 < 2 = log_2(4)

So we're in case 1 of the master theorem. By case 1, we have

F(n) = Theta(n^2)

So

T(2^n) = Theta(n^2)

Therefore

T(n) = Theta(log(n^2)) = Theta(2logn) = Theta(log n)

So yes, your answer seems to be correct.