-3
$\begingroup$

Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part

$\endgroup$
1
  • 1
    $\begingroup$ Substitute $n = 2^{2^k}$ in the entire expression. Can you solve the recurrence in terms of $k$? $\endgroup$
    – plshelp
    Sep 15, 2022 at 21:50

1 Answer 1

0
$\begingroup$

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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.