3
$\begingroup$

Trying to work out the following question, but I'm stuck.. Can someone direct me please.

  • Using a change of variables

    $ \text{Let}\ m = \lg\ n \\ S (m) = T (2m)\\ T (2^{m}) = T (2^{m/2}) + 2 \\ S( m) = S (m/2) + 2 $

  • Using Master Theorem

$ n\ log_b a = n\ log_2 1 = n^{0} = 1\text{ and }f (n) = 2 $

Since $ 1 < θ(2)$, case 1 applies and $S (m) = θ(\lg\ m^2), \quad\therefore T (n) \in \theta(\lg\lg{n^2}) $

or

I was also thinking about the problem like this: $\begin{align} T(n) &= T(\sqrt n ) + 2 = T(n^{1/2}) + 2 = T(n^{1/4}) + 4 = \cdots \\ &= T(n^{1/2^i}) + 2i = \cdots = T(n^{1/2^k}) + 2k\\ \end{align}$ $ n^{1/2^k} <=2 \\ \text{so } \log n = 1/(2^k) \\ k = \log (\frac{1}{\log n}) $ $ ∴ T (n) ∈ θ(\lg \lg n)\ or\ T(n)\ \in θ(\log (\frac{1}{\log n})) $

  • 0
    I did understood the chnage of variables, especially from line 2 to line 3 : $S(m)=T(2m)$ $T(2m)=T(2m/2)+2$ $S(m)=S(m/2)+2$2013-04-16

1 Answers 1

1

Let $n = a^{2^m}$. Then $\sqrt{n} = a^{2^m/2} = a^{2^{m-1}}$. Letting $T(a^{2^m}) = g(m)$, we get that $g(m) = g(m-1) + 2 = g(m-2) + 2 + 2 = g(m-3) + 2 + 2 +2 = g(0) + 2m$ Note that $\log_2(n) = 2^m \log_2(a) \implies \log_2(\log_2(n)) = m + \log_2(\log_2(a))$ Hence, $m = \log_2(\log_2(n)) - \log_2(\log_2(a))$ This gives us that $T(n) = 2 \log_2(\log_2(n)) - 2\log_2(\log_2(a)) + T(a)$ Hence, $T(n) = \mathcal{O}(\log_2(\log_2(n)))$

  • 0
    Why not write something like "for $n\gt 2$ you have $T(n) = k + 2 \times \lceil \log_2 (\log_2 (n))\rceil$"?2012-12-01