Results 1 to 12 of 12

Math Help - Why can I ignore a monotonic function?

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Why can I ignore a monotonic function?

    I am attempting to tackle a problem in a computer science course which involves taking a limit. I had gotten a piece of advice but I'm not quit sure about some of the details and I was hoping someone could give me some clarification.

    The problem is...

    Prove the is n\sqrt{\log{n}} is  \omega(\sqrt{n}\log{n})

    My book says that it comes down to showing that \lim_{x \to \infty} \frac{f(n)}{g(n)}} = \infty
    So I have to find \lim_{x \to \infty} \sqrt{\frac{n}{\log{n}}}}}

    I'm told that this is equivalent to finding \lim_{x \to \infty} \frac{n}{\log{n}}}} since the square root is monotonic.

    I can use L'Hopital's rule and show that the limit converges to infinity. I do understand why the square root function is monotonic but I don't understand why I'm allowed to disregard the affect of the square root on the function.
    Could someone explain why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Why can I ignore a monotonic function?

    The important thing is not that \sqrt{n} is monotonic, but that it tends to infinity as n -> ∞. For example, h(n) = 1 - 1 / n = (n - 1) / n is also monotonic for n > 0, but h(n / log(n)) = 1 - log(n) / n -> 1 as n -> ∞. Here h(n) -> 1 as n -> ∞ instead of h(n) -> ∞. On the other hand, h(n) = 2sin(n) + n is not monotonic, but h(n / log(n)) -> ∞.

    Can you prove that if j(n) -> ∞ and h(n) -> ∞ as n -> ∞, then h(j(n)) -> ∞ as n -> ∞?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by restin84 View Post
    I am attempting to tackle a problem in a computer science course which involves taking a limit. I had gotten a piece of advice but I'm not quit sure about some of the details and I was hoping someone could give me some clarification.
    The problem is...
    Prove the is n\sqrt{\log{n}} is  \omega(\sqrt{n}\log{n})
    My book says that it comes down to showing that \lim_{x \to \infty} \frac{f(n)}{g(n)}} = \infty
    So I have to find \lim_{x \to \infty} \sqrt{\frac{n}{\log{n}}}}}
    I'm told that this is equivalent to finding \lim_{x \to \infty} \frac{n}{\log{n}}}} since the square root is monotonic.
    I can use L'Hopital's rule and show that the limit converges to infinity. I do understand why the square root function is monotonic but I don't understand why I'm allowed to disregard the affect of the square root on the function.
    Will you please review what you posted.
    You explain nothing about the notation you are using.
    What is the actual question?
    What does  \omega(\sqrt{n}\log{n}) mean?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,423
    Thanks
    1332

    Re: Why can I ignore a monotonic function?

    I suspect that was supposed to be what some of use would have called " \theta" or " \Theta" or "O"- f is "O(g)" if and only if f(x)/g(x) goes to 1 as x goes to some limit such as infinity. Saying that x\sqrt{ln(x)}\epsilon \sqrt{x}ln(x) means that \lim_{x\to\infty}\frac{x \sqrt{ln(x}}{\sqrt{x}ln(x)}= \frac{x}{\sqrt{x}}\frac{\sqrt{ln(x)}}{ln(x)}=  \sqrt{\frac{\sqrt{x}}{ln(x)}} goes to 1 as x goes to infinity. Of course, since the square root function is continuous for x positive, that will be true as long as \lim_{x\to 0}\frac{\sqrt{x}}{ln(x)}= 1. And that can be shown by, for example, L'Hopital's rule.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by Plato View Post
    What is the actual question?
    I think the OP is asking why \lim_{x \to \infty} \frac{n}{\log{n}}}}=\infty implies \lim_{x \to \infty} \sqrt{\frac{n}{\log{n}}}}}=\infty.

    Quote Originally Posted by Plato View Post
    What does  \omega(\sqrt{n}\log{n}) mean?
    This is not really relevant to the question (because the problem reduces to proving \lim_{n\to\infty}\frac{n\sqrt{\log n}}{\sqrt{n}\log n}=\infty), but apparently this is one of the asymptotic notations.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by HallsofIvy View Post
    Saying that x\sqrt{ln(x)}\epsilon \sqrt{x}ln(x) means that \lim_{x\to\infty}\frac{x \sqrt{ln(x}}{\sqrt{x}ln(x)}= \frac{x}{\sqrt{x}}\frac{\sqrt{ln(x)}}{ln(x)}=  \sqrt{\frac{\sqrt{x}}{ln(x)}} goes to 1 as x goes to infinity. Of course, since the square root function is continuous for x positive, that will be true as long as \lim_{x\to 0}\frac{\sqrt{x}}{ln(x)}= 1. And that can be shown by, for example, L'Hopital's rule.
    Of course, neither \lim_{x\to 0}\frac{\sqrt{x}}{\ln(x)} nor \lim_{x\to \infty}\frac{\sqrt{x}}{\ln(x)} equals 1 (and it should say \lim_{x\to \infty}\frac{x}{\log(x)}). And none of big-O, big-Θ, and small-ω notations involve a limit that equals 1.
    Last edited by emakarov; September 22nd 2012 at 04:03 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by emakarov View Post
    I think the OP is asking why \lim_{x \to \infty} \frac{n}{\log{n}}}}=\infty implies \lim_{x \to \infty} \sqrt{\frac{n}{\log{n}}}}}=\infty.

    This is not really relevant to the question (because the problem reduces to proving \lim_{n\to\infty}\frac{n\sqrt{\log n}}{\sqrt{n}\log n}=\infty), but apparently this is one of the asymptotic notations.
    Why are we expected to make a guess as to what is meant?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by Plato View Post
    Why are we expected to make a guess as to what is meant?
    I feel the same way about some questions on this site, but in this case I think the question was pretty clear.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by emakarov View Post

    Can you prove that if j(n) -> ∞ and h(n) -> ∞ as n -> ∞, then h(j(n)) -> ∞ as n -> ∞?
    I was trying to find some information I could use in order to prove the above statement. I'm not really sure where to start.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by restin84 View Post
    I was trying to find some information I could use in order to prove the above statement. I'm not really sure where to start.
    You need prove that for every M > 0 there exists an N such that for every n > N it is the case that h(j(n)) > M. Fix an arbitrary M. Since h(n) -> ∞ as n -> ∞, there exists a K such that n > K implies h(n) > M. Now you need to guarantee that j(n) > K from some point onward. This would mean that h(j(n)) > M. Can you do this?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2011
    Posts
    22

    Re: Why can I ignore a monotonic function?

    Quote Originally Posted by emakarov View Post
    You need prove that for every M > 0 there exists an N such that for every n > N it is the case that h(j(n)) > M. Fix an arbitrary M. Since h(n) -> ∞ as n -> ∞, there exists a K such that n > K implies h(n) > M. Now you need to guarantee that j(n) > K from some point onward. This would mean that h(j(n)) > M. Can you do this?
    Honestly no. I've been reading it over for the last fifteen minutes now. I can't really get any kind of "mental picture" I guess.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Why can I ignore a monotonic function?

    The fact that j(n) > K from some point onward, i.e. that there exists an N such that n > N implies j(n) > K, follows by definition from the fact that j(n) -> ∞ as n -> ∞. Verify that h(j(n)) > M for n > N.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Integrability of monotonic decreasing function
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: December 11th 2009, 06:55 AM
  2. monotonic function
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 15th 2009, 10:21 AM
  3. Replies: 3
    Last Post: December 10th 2008, 11:32 AM
  4. Monotonic Convergence of a function
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 3rd 2008, 04:28 PM
  5. Show that the function is monotonic
    Posted in the Calculus Forum
    Replies: 12
    Last Post: February 17th 2008, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum