Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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?? –  DonAntonio Dec 1 '12 at 2:38
    
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. –  FrenzY DT. Dec 1 '12 at 2:40
1  
just did, first time doing it. Thanks for the feedback –  user51348 Dec 1 '12 at 2:47
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 Ccommands –  Ross Millikan Dec 1 '12 at 2:50
    
thanks for the feedback guys :), really appreciate it. –  user51348 Dec 1 '12 at 2:51

1 Answer 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)))$$

share|improve this answer
    
impressive, thanks :) –  user51348 Dec 1 '12 at 2:55
    
Why not write something like "for $n\gt 2$ you have $T(n) = k + 2 \times \lceil \log_2 (\log_2 (n))\rceil$"? –  Henry Dec 1 '12 at 3:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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