Solved

# Proving with Big-O notation

Posted on 2011-02-26
1,059 Views
Hey,

I was just thinking about Big-O notation... I was trying to prove n^2 = O(2^n).

This is a homework problem... so I don't expect a straight answer... but maybe a nudge in the right direction? =)

I never quite understood how Big-O worked... after dealing with math that had to be exact and precise... its kinda hard for me to wrap my head around this "almost" idea.

My initial thought about proving this statement was to say that the graphs of these two functions would behave in a similar way... but the gap between these two functions keeps increasing... (When n = 10; n^2 = 100 and 2^10 = 1024).

Then I thought that they might have similar slopes... and that's why they were equal, but their slopes were nowhere near each other...

The only thing I can see after re-reading the chapter was that both sides grew exponentially, and that's why they'r equal.

Am I on the right track?

Appreciate any help on this!
0
Question by:errang
• 7
• 5
• 5
• +1

LVL 84

Expert Comment

ID: 34990290
do you know the definition of f(n) = O(g(n)) ?
0

Author Comment

ID: 34990318
From what I understand max(f(n)) = O(g(n)).

Where max(f(n)) would give you the term with the highest exponent.

Am I right?
0

LVL 84

Expert Comment

ID: 34990339
not exactly
f(n) = O(g(n)) means that there exists a positive number M and a real number x0 such that
|f(x)| <= M*|g(x)| for all x > x0

so can you find any M and x0 such that
|x^2| <= M*|2^x| for all x > x0
0

Author Comment

ID: 34990369
Hm... I'm supposed to find an M that makes |x^2| <= M*|2^x| true? But... is M a constant?
0

LVL 84

Expert Comment

ID: 34990376
You are supposed to find a constant M and a constant x0 that makes |x^2| <= M*|2^x| true for all x > x0
0

LVL 84

Expert Comment

ID: 34990381
or prove that they exist without necessarily finding them, but in this case, finding such an M and x0 may be the
easiest way to prove that they exist.
0

Author Comment

ID: 34991360
Hm... I'm not entirely sure how to come with a constant for M because it is being multiplied by an exponential function... best I can do is make it 1/n^2

And make x0 = 5?
0

LVL 37

Accepted Solution

TommySzalapski earned 250 total points
ID: 34991901
Here's the (usually) easiest way to prove big O.
To prove f(n) = O(g(n)).
Look at the limit of f(n)/g(n) as n -> ininity
If the limit goes to 0 then f(n) is fundamentally 'smaller' than g(n) so f(n) = O(g(n)) (also f(n) = little o(f(n)))
If the limit equals some constant between 0 and infinity then they are similar so f(n) = O(g(n)) (also f(n) = big theta(f(n)))
If the limit is infinite, then f(n) does not equal O(f(n)) (also f(n) = little omega(f(n)))

If you don't know about little o, theta and omega then don't worry about it. I'll mention them just for fun
big O is like <=
little o is like <
big theta is like =
big omega is like >=
little omega is like >

Anyway. If the limit is not infinite then big O is true. The value of the limit will also give you a nice M for proving by the definition (Ozo's method) for most cases.

0

LVL 84

Assisted Solution

ozo earned 250 total points
ID: 34992446
|x^2| <= M*|2^x| for all x > 5
is true for some M
Can you find such an M?
There can be more than one possible M, and you do not need to find the smallest one.
0

Author Closing Comment

ID: 34992782
Ah... sweet, got it, thanks! =)
0

Author Comment

ID: 34992886
Hm... I used the L'hopital's rule to get the limit of f(n)/g(n) and I ended up with a 2...

But that doesn't seem right... does it? I mean, 2^n is already bigger than n^2
0

LVL 37

Expert Comment

ID: 34993436
You must have done it wrong. What did you get as the derivative of 2^n? It's 2^n*ln(2)
2^n/n^2
L'H
(2^n*ln(2))/2n
L'H again
(2^n*ln(2)^2)/2
Clearly this goes to infinity.
0

LVL 37

Expert Comment

ID: 34993438
Rereading my post, it seems a bit blunt. It was not meant that way. The derivative of 2^n is not something I would expect you to know off the top of your head. It's a common mistake.
0

Author Comment

ID: 34993657
Ah... Yea, I used the power rule to get the derivative of 2^n.

But if it's f(n)/g(n), I'd get:
n^2/2^n, right? n^2 was f(n)

= 2/(2^n*ln(2)^2)

So the limit would go to 0?
0

LVL 37

Expert Comment

ID: 34994416
Yes it would go to 0. So f(n) = O(g(n)) since n^2 is certainly less than 2^n as n gets large.
Remember O is like <= so f(n) = O(g(n)) if f(n) is a lot smaller or roughly the same. In this case, it's definitely a lot smaller (note, most professors will cringe at my use 'smaller' since it's such a non technical word). The technical way to say it would be n^2 = o(2^n). That's little o. Little o always means big O is true too.
Since it goes to 0 that means f(n) = O(g(n)) but g(n) does not = O(f(n))
If the limit happens to be a constant, then both ways are true.
0

Author Comment

ID: 34994453
Ah... sweet, thanks a lot!
0

LVL 20

Expert Comment

ID: 35497479
@TommySzalap:
Actually, professors ma also cringe at your assumption of existing limits, for example sin(x) = O(1) even though sin(x)/1 does not converge as x -> oo. Instead of "finite limit" we need only (eventually) "bounded" - as in the M and x0 definition ozo mentioned above
0

LVL 37

Expert Comment

ID: 35506936
Yes, if a limit does not exist, you would need to add some additional tools to get it all working. If the limit does not exist but the function is bounded, then you can use the bounds.
Ozo's method works too but is often harder to do and you would need to prove f = O(g) and g = O(f) to show big theta.

It's good to have both methods in your toolbox though.
0

## Join & Write a Comment Already a member? Login.

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp aâ€¦
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every montâ€¦
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the fileâ€¦
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: â€¦

#### 747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!