Week 9 & 10

In weeks 9 and 10 we learned about Big-Oh, Big-Omega, and Big-Theta.

Let's say we had the functions f(n) and g(n). The Big-3 essentially define the relationship between the growth of such functions as n approaches infinity.

In layman's terms:

1) f(n) is in Big-Oh of g(n) means that as n approaches infinity, the value of f(n) is always equal to or less than that of g(n)

2) f(n) is in Big-Omega of g(n) means that as n approaches infinity, the value of f(n) is always equal to or greater than that of g(n)

3) f(n) is in Big-Theta of g(n) means that as n approaches infinity, the value of f(n) is always equal to g(n), or greater than some constant*g(n) and less than some other constant*g(n)

There are many important practical applications of these definitions. For example, when you are interested in finding out how the polynomial running time of one algorithm compares to another, you can formalize such a comparison by defining their relationship in terms of statements 1 through 3. This creates a common basis for the communication of algorithm run-time comparisons between computer scientists and removes unnecessary ambiguity.