Video: The Mathematics of Big-O
Big O Mathematics
Consider the following, somewhat counter-intuitive Big-O principles and their consequences:
O(c * n) == O(n) Example: O(2n) == O(3n) == O(n)
O(n+c) == O(n) + c == O(n) Example: O(n+57) == O(n)
If the above examples are confusing, try to think of end behavior in your Algebra 2 class when doing Big O analysis. We use only the leading term to determine end behavior for a polynomial. Likewise, when analyzing the efficiency of a computer program given as a polynomial, only the leading term needs to be considered. Constants, smaller terms, and coefficients have little impact on a program as n gets very large.
The following video on the mathematics of Big-O, Big Omega, and Big Theta will hopefully help to cement your understanding of these concepts.
Differences Between Mathematical and Computer Science Terminology With Respect to Big-O
Consider a computer program that takes the following number of seconds to process n entries:
F(n) = 4n2 + 16n + 2
A mathematician would say that F(n) is Big-O of n-squared (written as O(n2)) and also Big Theta of n-squared. The mathematician would also say that F(n) is also O(n3) and O(n4), etc. When talking about the tighest bound (n-squared), mathematicians would use the Big Theta notation to denote that.
However, Computer Scientists do not want to bother with three different terms: Big-O, Big Omega, and Big Theta. So when Computer Scientists use the term Big-O, they are typically referring to the tightest bound only. So a Computer Scientist would say that this function is O(n2) but would never say it is O(n3).
If you still do not understand this subtle but important difference in the terminology of Big-O between the mathematicians and Computer Scientists, please review this topic with your instructor.
For the remainder of this course, our definition of Big-O will be that used by Computer Scientists (what the mathematicians call Big Theta).