# Thread: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

1. ## $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

Hi all

How can I prove the following?

$\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

2. ## Re: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

What does "$\displaystyle \Theta$" mean here? An asymptotic bound?

3. ## Re: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

yes sir!. I am completely new to this and cannot know how to do this while understanding a paper!

4. ## Re: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

A little algebra might help:

$\dfrac{n}{k\ln n} \ln \dfrac{n}{\ln n} = \dfrac{n}{k\ln n}\big( \ln n - \ln (\ln n ) \big) = \dfrac{n}{k} - \dfrac{n\ln ( \ln n ) }{k \ln n}$

So, your goal seems to be to show that $\dfrac{n\ln ( \ln n ) }{k \ln n}$ is dominated by $\dfrac{n}{k}$.

5. ## Re: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

Actually, I missed a step:

$\dfrac{n}{k}-\dfrac{n \ln ( \ln n ) }{k \ln n} = \dfrac{n}{k}\left( 1 - \dfrac{ \ln ( \ln n ) }{ \ln n } \right)$

Now, by L'Hospital's Rule:

\begin{align*}\displaystyle \lim_{n \to \infty } \dfrac{ \ln ( \ln n ) }{ \ln n } & = \lim_{n \to \infty } \dfrac{\left( \dfrac{ \cancel{ \dfrac{1}{n} } }{ \ln n } \right) }{ \cancel{ \dfrac{1}{n} } } \\ & = \lim_{n \to \infty } \dfrac{1}{\ln n} = 0\end{align*}

So, $\Theta \left( \dfrac{n}{k}\left( 1 - \dfrac{\ln ( \ln n ) }{\ln n} \right) \right) = \Theta \left( \dfrac{n}{k} \right)$

6. ## Re: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

Originally Posted by SlipEternal
Actually, I missed a step:

$\dfrac{n}{k}-\dfrac{n \ln ( \ln n ) }{k \ln n} = \dfrac{n}{k}\left( 1 - \dfrac{ \ln ( \ln n ) }{ \ln n } \right)$

Now, by L'Hospital's Rule:

\begin{align*}\displaystyle \lim_{n \to \infty } \dfrac{ \ln ( \ln n ) }{ \ln n } & = \lim_{n \to \infty } \dfrac{\left( \dfrac{ \cancel{ \dfrac{1}{n} } }{ \ln n } \right) }{ \cancel{ \dfrac{1}{n} } } \\ & = \lim_{n \to \infty } \dfrac{1}{\ln n} = 0\end{align*}

So, $\Theta \left( \dfrac{n}{k}\left( 1 - \dfrac{\ln ( \ln n ) }{\ln n} \right) \right) = \Theta \left( \dfrac{n}{k} \right)$
So you mean that when $\Theta$ is removed, we have to take $n \to \infty$

7. ## Re: $\Theta (\frac{n}{k \ln n} \ln \frac{n}{\ln n}) = \Theta(\frac{n}{k})$

Originally Posted by sjaffry
So you mean that when $\Theta$ is removed, we have to take $n \to \infty$
Not quite what I meant. I used the limit as $n\to \infty$ is used to demonstrate that asymptotically, $\left(1-\dfrac{\ln ( \ln n ) }{\ln n} \right) \sim 1$.