Week 9 Big-O and Big-Omega of Polynomials and Other Functions

Following up from my last post, I'm finally coming around to the idea that extraneous terms and constants that are not of the highest power in a polynomial are irrelevant.  In the long run, the highest power always wins and thus we need not worry about a slightly higher breakpoint.
With so many different types of classifications it definitely makes sense to use this simplified notation.

One thing I still don't quite see the use for is the lower bound big-Ω.  I understand that we are trying to establish the lower bound for the worst case, but if we extend this to the expected runtime for a random set of inputs, shouldn't we also include the input cases where the runtime is better than the worst case?  Thus rendering Big-Theta somewhat meaningless. Or is this another instance where we sweep things under the rug because they don't amount to anything significant, much like the coefficients, constants, and lower powered terms I mentioned earlier.

Its also interesting to see that the same function can be used to bound above and below. I guess this is another result have having the broad definition for big-O and big-Ω.

We covered similar topics in CSC148 where we very broadly classified various functions using the following asymptotic notations.  I have ordered them approximately from smallest to largest:
O(1) = constant time does not depend on the size of an input
O(k) = linear time based on some input value k
O(h) = linear time with the size or height of an internal data structure
O(logn) = logarithmic runtime typically encountered when traversing heaps
O(n) = linear runtime proportional to size n
O(nd) = runtime that is proportional to both the size of an input and the number of digits of the items of an input (radix sort)
O(nlogn) = runtime of mergesort typically
O(mn) = runtime is proportional to the size of two different inputs
O(n²) = quadratic runtime such as with insertion sort or selection sort
O(2ⁿ) = the worst of all the ones we've touched on

Overall, I am feeling good about working with asymptotic notation.  The concept seems intuitive at least for polynomial functions. Generally, it helps to have a graphing calculator handy so you can see the odd behavior for each function near the origin and for when n gets really large. I find that graphing the functions lets you develop that sixth sense for breakpoints and coefficients.  So far the trickiest part is making sure you choose the right coefficient c, and that you keep track of the minimum value for the breakpoint B. If there are constants involved for big-O then usually B is some value >= 1.  Also, c is usually >= 1 for big-O and < 1 for big-Ω.

Looking at some of the other slogs here is one that adds a nice touch using some of the lecture slides. I think this student also agrees that picking the right B and the right c for a proof is important. I let them know in the comments section of their blog.
http://ace165.blogspot.ca/2014/11/week-10-big-proof.html