CSC165: SLOG - More Asymptotics ---------------[ Week 10 ]--------------

The awesome sounding "big-Omega!" was introduced, and with a somewhat similar name came a relatively similar definition. As big-O was focused on a function being bounded above by another function, big-Omega focuses on a function being the upper bound of another function. The two definitions are entirely the same except for the inequality signs. Where big-Oh holds f(n) <= cg(n), and big-Omega holds f(n) >= cg(n). It also followed that a function can be bounded above and below by the same function ( f belongs to O(G) ^ f belongs to Omega(g) ). If this this concept is true, we represent it as "Big-Pheta", where c1*g(n) <= f(n) <= c2*g(n). The proof of general statements about two functions followed, as well as a big-O implying a big-Omega (f O(g) => g Omega(f)).

The proof of... f O(g) => f*f O(g*g), was shown on Wednesday as well as,
(f O(h) ^ g O(h)) => (f + g) O(h) and the disproof of f O(g) => f O(g*g)

On Friday we discussed patterns of linear search and derived formulas for the number of steps a linear search takes. We also discussed which of the three speed: best, worst, and average... was most important. In the end, the worst case proved itself to be the most important speed to which we care about since we are able to guarantee a lower bound, as in this search will be in the worst case ______, rather than saying the average and best speed (which is less valuable). And with all of this, we then finally proved that a certain sort was in the worst case bounded above by n^2. I believe this was the most confusing part of this week, in the fact that we didn't use a formula given but a formula we had to derive from the python code.

Nevertheless, this week was quite packed and was a bit hard to keep up with, I plan to go to the CSSU help center to go over these notes carefully, just to make sure I understand these new concepts.