Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Math Forum » Discussions » Math Topics » discretemath

Topic: Big O Proof
Replies: 3   Last Post: May 11, 2013 2:25 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Angela Richardson

Posts: 42
From: UK
Registered: 6/22/11
Re: Big O Proof
Posted: May 10, 2013 2:04 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply
att1.html (1.9 K)

For all c, k, n there exists x>k suct that tan(x)>cn^n:

Pick a positive integer m so that m*pi>k. Suppose n>1.

| lim_{x->m*pi+pi/2 from below} tan(x) / (c*n^x) | <= | [ lim_{x->m*pi+pi/2 from below} tan(x) ] / (c*n^x) | since |c*n^x| is increasing. The denominator is finite and the numerator tends to +infinity, therefore the fraction must become >1.

If tan(x) were O(n) for n<=1 then tan(x) would also be O(|n|+2) therefore the proof for n>1 is sufficient.

Just for fun: can you prove that tan(x) is not O(tan(tan(x)) but sin(x) is O(sin(sin(x))?

From: Nicolas Manoogian <discussions@mathforum.org>
To: discretemath@mathforum.org
Sent: Thursday, May 9, 2013 10:58 PM
Subject: Big O Proof

You guys have been awesome. I have one last proof this year and my professor is not letting up! I'm trying to prove that tan(x) is not Big O of n^x. My professor doesn't like my undefined argument.

He responded to my proof:
"Given c,k,n find s > k such that tan(x) > cn^x."

He also added:
"Don't forget case when n<=1!"

Now, do I want to be using limits? I really thought that I had the right solution!


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2015. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.