0
$\begingroup$

I've been given this recurrence to solve:

$T(n) = T(\sqrt n) + \theta(lglgn)$

And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows:

$S(m) = S(m/2) + \theta(lgm)$

But I don't understand how $T(\sqrt n)$ can become $S(m/2)$. Is there some key manipulation going on that I'm not seeing?

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

$$ \frac{1}{2} m = \frac{1}{2} \log n = \log n^\frac{1}{2} = \log \sqrt{n}$$ $$ S(\log n) = S(\log \sqrt{n}) + \Theta(\log \log n) $$

$\endgroup$
1
  • $\begingroup$ Great, thank you. I was missing that $\frac 12 log n = log n ^ \frac 12$. $\endgroup$ Commented Jun 28, 2014 at 19:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.