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

Topic: Big-O Notation Estimates
Replies: 2   Last Post: Oct 4, 2012 11:16 AM

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 Notation Estimates
Posted: Oct 4, 2012 3:35 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply
att1.html (2.1 K)

When x>2, x^2>2x and x^2>1 hence 3x^2>x^2+2x+1. f(x) is O(g(x)) if there exists C such that for all x>k, f(x)<=Cg(x), and in this case k=2 and C=3.

From: Joe <>
Sent: Thursday, 4 October 2012, 1:59
Subject: Big-O Notation Estimates


Im having some trouble understanding Big-O estimates. Im using Discrete Mathematics And Its Applications by Rosen 6th Edition. In section 3.2 one of the example problems says to show that f(x) - x^2 + 2x + 1 is O(x^2).

The solution states the following:

"We observe that we can readily estimate the size of f(x) when x > 1 because x < x^2 and 1 < x^2 when x > 1. It follows that

0 <= x^2 + 2x + 1 <= x^2 + 2x^2 + x^2 = 4x^2

whenever x > 1.
Consequently, we can take C = 4, k = 1 as witnesses to show that f(x) is O(x^2). That is, f(x) = x^2 + 2x + 1 = 4x^2 whenever x > 1.

I have read this so many times and for some reason the concept is not sticking. Im hoping someone can explain how this problem was worked. Here is what I dont understand:

Why is "0<=" being used here?
How did we go from x^2 + 2x + 1 to x^2 + 2x^2 + x^2?

I thought maybe we are using the value of g of x (x^2) to replace the x values in the f(x) function but should this not be x^4 + 2x^2 + 1?

Any help would be appreciated.

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-2017. All Rights Reserved.