Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

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

  1. #1
    Junior Member
    Joined
    Jun 2017
    From
    New Zealand
    Posts
    25

    $\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})$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,462
    Thanks
    2893

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

    What does " \Theta" mean here? An asymptotic bound?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2017
    From
    New Zealand
    Posts
    25

    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    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}$.
    Last edited by SlipEternal; Aug 28th 2017 at 06:41 AM.
    Thanks from sjaffry
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    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)$
    Thanks from sjaffry
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2017
    From
    New Zealand
    Posts
    25

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

    Quote Originally Posted by SlipEternal View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

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

    Quote Originally Posted by sjaffry View Post
    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$.
    Last edited by SlipEternal; Aug 29th 2017 at 06:28 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Dec 14th 2015, 07:32 AM
  2. Replies: 3
    Last Post: Dec 25th 2014, 12:58 AM
  3. Replies: 3
    Last Post: Oct 31st 2012, 04:58 PM
  4. Replies: 6
    Last Post: Mar 26th 2011, 07:05 AM
  5. [SOLVED] arg(z)=\frac{\pi}{4}
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Sep 5th 2010, 05:50 PM

/mathhelpforum @mathhelpforum