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
    Or you go to the FAQ section and learn (it's easy, btw) how to properly type mathematics in this site with LaTeX, or your post will be very hard to decypher for many participants here and, perhaps, you won't get all the help you could otherwise. Read, as a sad example, your 2nd line: what on earth could " m = lg n S (m)..." possible mean??2012-12-01
  • 0
    Please learn some $\LaTeX$ to format your posts. When I first came to this site I spent a few days learning it and now I'm rather sufficient at formatting. Plus, I love $\LaTeX$ now. Second, your "following question" is not embedded in your post.2012-12-01
  • 1
    just did, first time doing it. Thanks for the feedback2012-12-01
  • 3
    Thanks for and congratulations on a successful $\LaTeX$ update of your post. It makes it sooooo much easier to read. One small one-for functions like log, if you do \log you get $\log$ which is the proper font. I learned much of mine by right-clicking and selecting Show Math As -> TeX Ccommands2012-12-01
  • 0
    thanks for the feedback guys :), really appreciate it.2012-12-01
  • 0
    `\begin{align}`, `\in`, `\mathbb R`, `\frac{a}{b}`, `\sqrt[3]n`, `\lg`, `\LaTeX`, `\cdots`.2012-12-01
  • 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