solving recurrence T(n) = T(√n) + theta((lg lg n))

Question

My solution: let m = lg n. Then n = 2^m. T(2^m) = T(2^(m/2)) + theta(lgm). Let S(m) = T(2^m). Then S(m) = S(m/2) + theta(lgm). Applying master theorem, I get m^(lg1) = 1 which is asymptotically smaller than theta(lgm). So I think case 3 of the master theorem should apply. However, the solution given explains that case 2 of the master theorem applies here which I do not quite understand.

Answer 1

Let $S(n) = T(2^n)$. Write a recurrence formula for S, solve S(n), use that to solve T(n).

Answer 2

T(n) = T(√n) + ϴ(log log n) …….1
Let n = 2^m
Taking log2 both side, we get
log₂n = m ……2
=> (log n) /log 2 = m (using the formula log_ab = log_mb /log_ma)
=> log n = m x log2
Now, equation 1 becomes
T(2^m) = T(2^(m/2)) + ϴ(log (m x log2))
=> T(2^m) = T(2^(m/2)) + ϴ(log (m) + loglog2))
As we know that constant can be ignored hence loglog2 can be ignored
=> T(2^m) = T(2^(m/2)) + ϴ(log m) …….3
Now, let T(2^m) = S(m) ……4
then T(2^(m/2)) = S(m/2)
So eq. 2 becomes:
S(m) = S(m/2) + ϴ(log m)
Now it is in master’s form, i.e T(n) = aT(n/b) + ϴ(n^k x log^p n)
here a = 1, b= 2, k = 0 , p = 1
which follows the case a = b^k, where p > -1
Hence S(m) = ϴ(m^log_ba x log^(p+1) m)
=> S(m) = ϴ(m^log₂1 x log² m)
=> S(m) = ϴ(m⁰ x log² m)
=> S(m) = ϴ(log² m)
Substituting S(m) with T(2^m) from eq. 4
T(2^m) = ϴ(log² m)
Now substituting the value of m from equation 2, we get
T(n) = ϴ(log² log₂n)
Thus it doesn't matter what base is log the answer will be same taking log both side instead of log₂ will make our job more easier.