Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part
1
-
1$\begingroup$ Substitute $n = 2^{2^k}$ in the entire expression. Can you solve the recurrence in terms of $k$? $\endgroup$– plshelpSep 15, 2022 at 21:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Hint:
Assuming base $2$ logarithms, we can write
$$\begin{align}T(65536)&=2T(256)+4^2\\&=4T(16)+2\cdot3^2+4^2\\&=8T(4)+4\cdot2^2+2\cdot3^2+4^2\\&=16T(2)+8\cdot1^2+4\cdot2^2+2\cdot3^2+4^2\end{align}$$
Hence, generalizing the pattern, you see the sum
$$\sum_{k=1}^{\lg(\lg(n))}{k^22^{\lg(\lg(n))-k}}=\lg(n)\sum_{k=1}^{\lg(\lg(n))}{k^22^{-k}}$$ appear, as well as a term $$\lg(n)T(2).$$
