Be seen. Boost your questionâ€™s priority for more expert views and faster solutions

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!

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!

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

Am I right?

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

easiest way to prove that they exist.

And make x0 = 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.

But that doesn't seem right... does it? I mean, 2^n is already bigger than n^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.

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?

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.

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

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.

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.

All Courses

From novice to tech pro — start learning today.

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.