The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Math Topics » discretemath

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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 <>
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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.