Big Oh Notation - formal definition.

Question

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! :(

Answer 1

50n <= 50n^2 for n >= 50

because if n is 50, then 50n is the same as n^2, because 50*50 equals 50^2.

Substituting n^2 for 50n we get

n^2 <= 50n^2 for n >= 50

which is obvious.

Answer 2

The whole thing about picking numbers is just this: To make it easier. Because you're allowed to pick any numbers you like for N and c, the author just picks something, where it's most easy to see. And that's what you can also do (when writing an exam etc).

So while it would often be possible to use a smaller N, the reasoning would become a little bit harder (often requiring some previous knowledge about analysis - we've all learnt years before, that x doesn't grow as fast as x^2... But do you want to write down the analysis proof?)

Keep it simple, is the message :-) It's just a bit strange to get used to this at first.

Answer 3

Keep in mind that you're looking for "an upper bound on f(n) when n is sufficiently large." Thus, if you can show that f(n) is less than or equal to some c*g(n) for values of n greater than N, this means c*g(n) is an upper bound for f(n) and f(n)'s complexity is therefore O(g(n)).

The examples given are intended to show that the given function f(n) can never grow beyond c*g(n) for any n > N. By manipulating an initial upper bound so it can be expressed more simply (if 4n^2 + 50n is an upper bound on f(n) then so is 4n^2 + 50n^2, which is equal to 54n^2, which becomes your 54*g(n) where c = 54 and g(n) = n^2), the authors can show that f(n) is bounded by c*g(n), which has complexity O(g(n)) and therefore so does f(n).

Answer 4

Probably the reason that they said 50n<=50n^2 for n>=50 is that if n is less than 1, than n^2 < n. Of course, if n is a positive integer, then yes 50n<=50n^2. In this case, it seems that n is assumed to be a positive integer, although the formal definition they give doesn't state that explicitly.

I can see why saying 50n<=50n^2 for n>=50 may seem a little silly. But it's still true. The book doesn't say 50n<=50n^2 holds ONLY for n>=50; that would be false.

As an analogy, if I say "all of my siblings speak English", that would be true, even though there are a lot of people who speak English who are not my siblings.

Regarding the proof, we might split it into different statements.

 (1): 4n^2 + 50n - 10 <= 4n^2 + 50n  (for all n)
 (2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50)  
 (3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50)
 (4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50
 (5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54, 
           the statement  f(n) <= c g(n) for all n >= N is true
 (6): Therefore, by definition 4n^2 + 50n - 10=O(n^2). 

It should be clear that each of these statements is true, either on its own (1,2,3), or as a result of the previous statements.

Answer 5

Formal definition:

• f(n) = O(g(n)) means there exist c > 0 and n₀ such that for any n >= n₀ f(n) <= c*g(n)
• f(n) = o(g(n)) means for any c > 0 there exist n₀ such that for any n >= n₀ f(n) <= c*g(n)

As you can note there are slightly different :)