# Proving with Big-O notation

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!
###### Who is Participating?

x

Commented:
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

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

Author Commented:
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

Commented:
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 Commented:
Hm... I'm supposed to find an M that makes |x^2| <= M*|2^x| true? But... is M a constant?
0

Commented:
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

Commented:
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 Commented:
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

Commented:
|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 Commented:
Ah... sweet, got it, thanks! =)
0

Author Commented:
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

Commented:
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

Commented:
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 Commented:
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

Commented:
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 Commented:
Ah... sweet, thanks a lot!
0

Commented:
@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

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.