Solved

Proving with Big-O notation

Posted on 2011-02-26
18
1,108 Views
Last Modified: 2012-05-11
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
Comment
Question by:errang
  • 7
  • 5
  • 5
  • +1
18 Comments
 
LVL 84

Expert Comment

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

Author Comment

by:errang
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

by:ozo
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
Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

 

Author Comment

by:errang
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

by:ozo
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

by:ozo
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

by:errang
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

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

by:ozo
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

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

Author Comment

by:errang
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

by:TommySzalapski
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

by:TommySzalapski
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

by:errang
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

by:TommySzalapski
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

by:errang
ID: 34994453
Ah... sweet, thanks a lot!
0
 
LVL 20

Expert Comment

by:thehagman
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

by:TommySzalapski
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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
read a line from a file and convert to a command in ksh 2 96
How to determine sequence 8 92
Two list de-cypher 6 101
sorting efficency of sorting algorithm 30 121
This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

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

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

Join & Ask a Question