Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$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?


share|cite|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
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
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|cite|improve this answer

Your Answer


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