Week 8: Intro to Big O and Big Omega

In this week's lectures,we were introduced to the notation of Big-Oh and Big-Omega, which is merely the two assessment used to test how efficient an algorithm is. As I mentioned in last week's slog, it is extremely important for an programmer/software developer to know the running time and efficiency of his algorithms. 

Big O specifically describes the worst-case scenario, and can be used to describe the execution time required by an algorithm. O(N), for example, describes an algorithm whose performance grows linearly and in direct proportion to the size of the input data. O(N2), on the other hand, represents an algorithm whose performance is directly proportional to the square of the size of the input data. The more formal definition, mentioned by professor in class, for O(n^2) is that beyond a breakpoint B, f(n) is upper bounded by cn^2, where c is a constant multiplier.Big Omega, which is completely the opposite of Big O, is used to describe the best case running time for a given algorithm.

Sometimes, people also describe Big O and Big Omega as bounds: Big O represents the upper bound running time for an algorithm, which is also the “worst case” whereas Big Omega is used to represent the lower bound, which is also the “best case” for that algorithm.