Big-O notation explained by a self-taught programmer

What you said is not very correct too! Big O tells about the "order of Growth of a function or the Growth rate", that's it. It gives a larger view of the function. Seeing from 1000 feet above the ground.

Link: http://web.mit.edu/16.070/www/lecture/big_o.pdf

My understanding --

A bounding function is when we know the exact function and its end-points from an algorithm. We know the extremes. i.e C1 and C2. i.e a Function falls within that boundary, it will always stay within that box(end-points). C1 and C2 are 2 lines, making a rectangle.

- Worst case, Best case, average case are different input cases, under which the algorithm grows in different ways. And we use BigO notation to classify them under easier functions, based on the order of Growth of a function.

And unless we don't know that exact function, its not possible to predict for any input variables. So don't call Big O as any bounding function, unless we know c1 and c2 .

- Big O is a notation that characterizes functions according to their growth rates.

- Different functions with the same growth rate may be represented using the same O notation.

- The letter O is used because the growth rate of a function is also referred to as order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

The post is kind of misleading because it confuses "order of magnitude" with the order of a polynomial. To make this very clear:

You have two functions, x^4 and x^3. You can multiply x^3 by any constant multiple a (any number, regardless of size), and as x gets sufficiently large x^4 will be bigger than a * x^3. This is the point of evaluating asymptotic performance: as your input data approaches an infinite size, only the highest order term in a polynomial really matters. For example, x^2 + x + 1 will approach x^2 for sufficiently large x - the lower order terms (x^1 and x^0) don't really matter for a big x.

Technically, big-O refers to a bounding function: x^2 is O(x^2) AND O(x^3), etc. because x^2 is less than or equal to x^2 and x^3 as you approach infinity. For convenience we're usually only interested in the best fit; it's useless to say your algorithm is faster than O(x^5), but it's interesting if it's O(n).

Finally, we also have small-oh notation, which is a lower bound. If your algorithm is never faster, on an ideal input set, than x^2, it's also o(x^2). Note that the same algorithm is also o(n) and o(1), because any algorithm which is slower than (or equal to) x^2 must necessarily be slower than x or 1 (constant-time).

edit: It's worth pointing out I only talked about polynomials because it's pretty intuitive. You can extend this notation to any class of functions - exponentials, logarithms, etc. but you just have to know that log(x) is O(x) and o(1), etc.

Big-O (or Ω or Θ) notation is orthogonal to notions of best-case or worst-case, which are merely constraints on the set of inputs we're considering. If, for example, you ask "what is the upper bound on best-case running time for linear search," then what you're actually asking is "given an input sequence that begins with the item being searched for, what is the upper bound on the running time." I think part of the confusion stems from the fact that when people supply bounds on best- or worst-case running times for deterministic algorithms, they often use Big-O notation when they're actually giving an asymptotically tight bound. So in the case of linear search's best case, O(1) is an upper bound, but the lower bound is of the same order, i.e. Ω(1). It's not incorrect, but it can be misleading.

In the case of Quicksort, I think the answer to your question is yeah, pretty much. I mean, cases where you're dealing with nearly-sorted input are common in some domains and in that case you should be very much aware of the worst-case behavior of Quicksort, but otherwise I think the discussion from CLRS puts things in perspective: even if you had the bad luck of only ever receiving input sequences such that every partitioning led to a 99-to-1 split, then your running time is still going to be O(n lg n), since your recursion tree is going to be at most log-base-100/99(n) levels tall, which is the same as lg n / (lg 100/99), the denominator there being a constant factor that disappears in an asymptotic context.

As a data point, I have no idea what you just said.

He's saying that big O only matters for big input sizes, because big O is specifically about the algorithm's asymptotic performance, which means its performance for a large value of n. If you have a small value of n then the other constant time operations in the algorithm may affect the running time more.

n^2 is less than n^3 right?

But is 2 * n^2 + 100 less than n^3?

Depends on how big n is, right?

Big O notation just assumes that n is big enough to make the answer "yes."