# 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) = 4n ^{2} + 16n + 2*

A mathematician would say that F(n) is Big-O of n-squared (written as O(n^{2})) and also Big Theta of n-squared. The mathematician would also say that F(n) is also O(n^{3}) and O(n^{4}), 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(n^{2}) but would never say it is O(n^{3}).

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).