Big O notation explanation in simple terms

Big O notation explanation

Note#1

When we develop an algorithm to solve a problem, we want to know about its growth rate (complexity) when the problem size becomes extremely large.

Note#2

Among of the algorithms for solving a problem, based on the observed/defined complexity, we can select a proper algorithm which requires less time or produces faster response for a problem based on the size and characteristics of the input.

For example:

  • When we have to select a sorting algorithm for a list of integers > 10,000 elements, it is clear that we should choose MergeSort or QuickSort instead of BubbleSort because the worst-case of Merge Sort and QuickSort is O(nlogn) while the worst-case of Bubble Sort is O(n^2).

  • However, if the elements are small like < 10 elements , then there is no big difference - sometimes BubbleSort is faster MergeSort or QuickSort - that’s why it is necessary to analyze the characteristics of the inputs before picking an algorithm for a problem.

  • Below graph shows the growth rate increases as the problem size become large - see why O(n2) is more complex than O(nlogn)

Note#3

So, we understand why we need to evaluate the complexity of an algorithm. Now, we will learn why people use the Big-O notation term for describing the complexity of an algorithm. If we have an algorithm with the time it takes to complete a problem of size n is:

T(n) = 12754n^2 + 4353n + 834lg2n + 13546.

What do you think? It is quite complicated and hard to evaluate it with other algorithms, right? So, we need to use a simpler model for easy evaluation - we want to ignore levels of detail that do not impact our algorithm when the input size becomes extremely large. By doing that, we simplify the complexity of the function. Intuitively, from the above T(n), we can see that when n becomes very large, the part 12754n^2 dominates the result of T(n).

Note#4

But how do we know which part dominates or greatly affect the function T(n) if T(n) is a very complicated one? So, we need to use some concepts from Mathematics like asymptotic upper bound, lower bound. By using them, we can find a simpler asymptotic function g(n) that acts as an upper limit or lower limit of the function T(n) we want to evaluate. We will discuss about the upper bound for Big O analysis (for other bounds, you can read more in the book - Algorithm Design Manual).

In mathematics, a function g(n) is the upper bound of a function f(n) is defined at: f(n) = O(g(n) if there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

The following graph visualizes the definition of f(n) = O(g(n))


(Source: http://www2.hawaii.edu/~janst/311/Notes/Topic-03.html)


Based on that, if we have an algorithm with T(n) = 3n^2 − 100n + 6.

  • We can say that T(n) = 3n2 − 100n + 6 = O(n^2), because if we choose c = 3 then we have 3n2 > 3n2 − 100n + 6.

  • Is O(n^3) another upper bound of T(n)? Yes, it is.

But in evaluating complexity of an algorithm, we want to find a function g(n) that T(n) is asymptotic to for better comparison between algorithms. So in above case, we prefer the upper bound O(n^2) for describing the complexity.

Note#5

In conclusion, we use Big-O notation to relatively represent the complexity of an algorithm. Big-O notation is a simplified function that acts as an asymptotic upper bound of the complexity function of the algorithm. By using the simplified function, we can easily evaluate the growth rate of a function for picking a suitable algorithm for a problem with specific inputs.

Hope this helps!

References

1/ Algorithm Design Manual Book

2/ Big-O

Written on October 29, 2016