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.

$T_{3}=\Theta(n^{0.99}),\quad T_{2}=\Theta(n^{\log\log n}),\quad T_{1}=\Theta \left(\frac{n}{\log n}\right)$

I need to decide what is the relation (ratio?) between $ T_{1},\, T_{2},\, T_{3}$?

So by taking $\log$ on the three of them I came to conclusion that $ T_{3}>T_{1},\,T_{2}$.

$\log T_{3}=0.99n$, $\log T_{2}=(\log\log n)\log n$ and $\log T_{1}=\log n-\log\log n$

What do you think?

Thanks

share|improve this question
    
Could you expand a bit more? I think you made a mistake taking the log... –  Fabian Jul 9 '11 at 13:57
    
I added it. thanks –  user6163 Jul 9 '11 at 14:15
    
The general idea is right. But there are typos and little mistakes and gaps. –  André Nicolas Jul 9 '11 at 14:27
    
I think that the expression for $\log T_3$ is incorrect and that therefore you have come to the wrong conclusion. –  Fabian Jul 9 '11 at 14:41
2  
Nir: I removed the (theta-functions) tag. It is meant to be used for something completely different. –  t.b. Jul 9 '11 at 15:28

1 Answer 1

up vote 2 down vote accepted

Your idea with the log is correct. However, you took the log of $T_3$ incorrectly. Given the functions $T_1$, $T_2$, and $T_3$, you know that (taking the log of the definition of the $\Theta$-notation) $$ \log n - \log\log n + c_1 \leq \log T_1 \leq \log n - \log\log n + C_1,$$ $$ (\log\log n) \log n + c_2\leq \log T_2 \leq (\log\log n) \log n + C_2,$$ $$ 0.99 \log n + c_3\leq \log T_3 \leq 0.99 \log n + C_3,$$ for $n> n_0$.

For $n$ large, $\log \log n> 1 > 0.99$ and thus $T_2> T_1 > T_3$.

share|improve this answer

Your Answer

 
discard

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