Explaining algorithm proofs in plain English

Question

I'm a programmer who never studied Algorithms formally, and have always wanted to fill in that gap in my learning. I'm currently working my way through some books and online material, and I understand conceptually Big O, i.e. what it's for, and the different categories of performance, e.g. constant, linear, quadratic, etc. I can code up problems and intuitively understand the performance implications of different approaches.

However, the thing I keep getting stuck at is the notation for proof of an algorithm, and I'm not sure where to look to figure this part out. All the books I've looked at assume this level of knowledge.

For example, this statement from Skiena's Algorithm Design Manual has me stumped:

f(n) = O(g(n)) means c * g(n) is an upper bound on f(n).

Thus there exists some constant c such that f(n) is always ≤ c * g(n), for large enough n (i.e. n ≥ n0 for some constant n0).

This is the corollary exercise the reader should complete:

3n^2 − 100n + 6 = O(n^2), because I choose c = 3 and 3n^2 > 3n^2− 100n + 6;

I can make some sense of both statements, and can logically see that the second one holds true. I also understand the concept of upper bound, i.e. this is for the worst case scenario.

But I'm stuck on simple things like, what do the following above refer to?

• g(n)

• n ≥ n0 for some constant n0

Overall, I can't put the pieces together to make sense of the entire proof.

Can anyone help me parse the above statements in plain English, and show how they relate to the exercise, in a way that would make sense to someone non-technical

Answer 1

The main problem here is that you are not used to the idioms used in maths.

Let's go phrase by phrase:

1. f(n) = O(g(n)) means c * g(n) is an upper bound on f(n).

   Plain English: Hey, writing c * g(n) is an upper bound on f(n) is too much work for me and I'll be using that a lot from here on. From now on, each time I want to say that, I'll write f(n) = O(g(n)). Also, f(n) and g(n) are just functions, I don't care which one as long as they take some integer n as argument and return some real value. The c is just some constant such that affirmation I made above is true. Remember that I'm not saying anything about complexity, about f or about g, I'm just creating a shortcut to say c * g(n) is an upper bound on f(n).

2. Thus there exists some constant c such that f(n) is always ≤ c * g(n), for large enough n (i.e. n ≥ n0 for some constant n0).

   Plain English: Just in case you didn't know, I'll recall you what an upper bound to a function is. A function g(n) is an upper bound of f(n) if you can find me one constant (that we will call c) such that f(n) ≤ c * g(n) for large enough n. You are surely wondering what large enough means, are you? We just mean that f(n) ≤ c * g(n) has to be true for all n bigger than a certain number. We do not know which number it is and we do not care to know, because the only thing that matters for us is that that number exists! We will just call it n0 so that we can say that n is large enough if n ≥ n0.

3. 3n^2 − 100n + 6 = O(n^2), because I choose c = 3 and 3n^2 > 3n^2− 100n + 6;

   Plain English: Now let's try an example just to show how it works. When I write 3n^2 − 100n + 6 = O(n^2) we have that f(n) = 3n^2 − 100n + 6 and g(n) = n^2. See what I did there? The fact that I did not say what f(n) and g(n) were before lets me put any function instead.

   As you can see all I mean here is that the phrase c * n^2 is an upper bound on 3n^2 − 100n + 6. This is an affirmation that can be true or false. The definition of upper bound will let us know how to decide if it is true. One way to prove that the affirmation is true is to find some number c and some number n0 such that 3n^2 − 100n + 6 ≤ c * n^2, for all n ≥ n0. If we try with c = 3, we have to prove 3n^2 − 100n + 6 ≤ 3 * n^2 for all n > n0, this is equivalent to proving -100n + 6 ≤ 0, for some n > n0. Finally we can say that for it to be true, we need n0 ≥ 6/100. We have found our n0 and we have proved that the whole affirmation is true

Your problem in my opinion is that you want things to be concrete. Mathematics on the other side tries to be abstract. That's why it mentions functions f and g without saying what they actually are. You just need to know they are functions and that as functions they have certain properties. The idea is that you want to reason about the properties of functions and not about some concrete functions. The same thing is valid for the n0, you just care about its existence, not about its value. If it exists, you can take it into account into your reasoning.

I hope my answer has helped you.

Answer 2

I hope you still have use for an answer :).

g(n) is the function you're comparing f(n), which is the real runtime, to. For example, you'd say Bubble Sort is O(n^2), making g(n)=n^2. However, intuitively, your algorithm won't take exactly n^2 time units (whatever time unit you might want to insert here); it might take 3n^2 − 100n + 6 (which is f(n)) time units, however.

Now, what Big-Oh notation does is comparing how fast two functions grow; this is a very coarse comparison, mind you. For example, it does not differentiate algorithms that need f(n)=n^2 time units from others that need f(n)=5n^2, neither does it differentiate between ones with f(n)=n^2 and others with f(n)=n^2+n. This is where c comes into play -- if you can find any constant c that you can multiply g(n) with, so that the resulting function returns a value bigger than f(n) for every n, then f(n) = O(g(n)).

What the Big-Oh notation also does is looking at is the fastest-growing part of f(n). Suppose you'd like to compare f(n) = n+100 to g(n) = n. Intuitively, f(n) = O(g(n)), but there's no c you can multiply g(n) with so that it is always bigger than f(n); however, n is obviously growing faster than 100, which is not growing at all. This is where, finally, n0 comes into play: The Big-Oh notation "tolerates" it if a for a finite number of n's, c*g(n) is not greater than f(n), as long as it is greater for an infinite number of n's. This finite number is given with n0 For example, for all n < 1 (which is a finite amount: exactly the number 0), f(n)=n+100 can be bigger than c*g(n) = c*n as long as for all other n's (an infinite amount: all numbers >=1, making n0=1) f(n) is smaller.