What is Big-O?
Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
According to Wikipedia, “Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.” For computer science, we use Big O notation to group algorithms by their runtime. Essentially, big O describes the function that a particular algorithm’s runtime is bound by, more specifically its upper bound. Consider the following function:
T(n) = 73n^3+ 22n^2 + 58There are a couple of things we can say about our function.
- T(n) = O(n¹⁰⁰)
- T(n) = O(n³)
- T(n) = Θ(n³)
First off, you might have noticed our function inside the parentheses looks like a stripped down version of the original function. The reason for this is when you consider ’n’ as it’s increasing to infinity, you will notice one part of the original function is impacting the runtime the most. In this case, its n³. The general rule is to look at the part of the function with the highest power and drop the constant if there is one. For our example you would take 73n³ and drop the constant 73. The result is n³, which we can then say — — — — T(n) = O(n³). It’s also important to note the equal sign in our equations does not mean T(n) is equal to O(n³). It’s saying the upper bound of T(n)’s runtime is the function n³, or T(n) grows asymptotically no faster than n³.
T(n) = 73n^3+ 22n^2 + 58- T(n) = O(n¹⁰⁰)
- T(n) = O(n³)
- T(n) = Θ(n³)
Next, let’s look at the accuracy of each statement. While number 1 may be true, it’s not the best upper bound we can come up with for T(n). The goal when determining big O is to find the most accurate upper bound of your function. Therefore, number 2 would be a much better answer. Depending on where you look, you might also see number 3 used to describe a function. Big theta (Θ(n)) is more accurate in many cases because it’s not feasible to determine the exact time complexity of an algorithm. It will usually give a more accurate description of an algorithm’s runtime because it is an intersection of both big O and another notation called big Omega (Ω(n)). Basically, big theta gives you an upper and lower bound for your runtime. However, O(n) is the strongest statement we can make if you can determine it.

Above is a visual representation of big O notation. You can see that, given a large enough n, the runtime of our algorithm, in red, is at most k * f(n), for some constant k. The red line never goes above the blue line after a certain point, i.e. give a large enough n.
Final Thoughts
Big-O notation, as well as other related notations, is one of the most important concepts to understand in computer science. I highly suggest you do your own research on the topic to gain a better understanding of its importance and use.