Big Oh Notation - formal definition.
- by aloh
I'm reading a textbook right now for my Java III class. We're reading about Big-Oh and I'm a little confused by its formal definition.
Formal Definition: "A function f(n) is of order at most g(n) - that is, f(n) = O(g(n)) - if a positive real number c and positive integer N exist such that f(n) <= c g(n) for all n = N. That is, c g(n) is an upper bound on f(n) when n is sufficiently large."
Ok, that makes sense. But hold on, keep reading...the book gave me this example:
"In segment 9.14, we said that an algorithm that uses 5n + 3 operations is O(n). We now can show that 5n + 3 = O(n) by using the formal definition of Big Oh.
When n = 3, 5n + 3 <= 5n + n = 6n. Thus, if we let f(n) = 5n + 3, g(n) = n, c = 6, N = 3, we have shown that f(n) <= 6 g(n) for n = 3, or 5n + 3 = O(n). That is, if an algorithm requires time directly proportional to 5n + 3, it is O(n)."
Ok, this kind of makes sense to me. They're saying that if n = 3 or greater, 5n + 3 takes less time than if n was less than 3 - thus 5n + n = 6n - right? Makes sense, since if n was 2, 5n + 3 = 13 while 6n = 12 but when n is 3 or greater 5n + 3 will always be less than or equal to 6n.
Here's where I get confused. They give me another example:
Example 2: "Let's show that 4n^2 + 50n - 10 = O(n^2).
It is easy to see that: 4n^2 + 50n - 10 <= 4n^2 + 50n for any n.
Since 50n <= 50n^2 for n = 50, 4n^2 + 50n - 10 <= 4n^2 + 50n^2 = 54n^2 for n = 50.
Thus, with c = 54 and N = 50, we have shown that 4n^2 + 50n - 10 = O(n^2)."
This statement doesn't make sense: 50n <= 50n^2 for n = 50.
Isn't any n going to make the 50n less than 50n^2? Not just greater than or equal to 50? Why did they even mention that 50n <= 50n^2? What does that have to do with the problem?
Also, 4n^2 + 50n - 10 <= 4n^2 + 50n^2 = 54n^2 for n = 50 is going to be true no matter what n is.
And how in the world does picking numbers show that f(n) = O(g(n))?
Please help me understand! :(
