Introduction to Big O Notation
Big O Notation
Big O Notation is used to describe the relationship between the size of the input and the running time of the algorithm. It is a crucial factor to look at when we need to evaluate the efficiency/performance of an algorithm.
Writing in Big O Notation
Big O Notation is denoted by the syntax O(expr). The expression inside is usually in terms of n, where n is the size of the input.
To figure out the complexity of a given algorithm:
Evaluate the amount of operations that each step does relative to the input size
Keep the term with the largest growth rate (for example, f(n) = n^2 grows more than f(n) = 2n when the magnitude of n increases)
In the growth rate, any constant term that does not depend on the size of the input n can be seen as 1, i.e. n+2 and 2n+100 are equivalent
For example, suppose a program does:
1. print out all of the letters of an input string
2. print out the string "apple"
The equations to represent the complexity of each line would be
1. time to print a single letter * the length of the input string
2. time to print a single letter * the length of "apple" which is 5
Given that the time it takes to print a single letter is the constant t, Step 1 takes t * n time where n is the length of the input string, which experiences a linear growth as the length of the input increases (O(n)). While Step 2 takes t * 5, which remains constant no matter how big the input size is (O(1)). Hence we consider Step 1 to have a greater growth rate than Step 2. Considering the two steps as functions of n, this process is essentially examining the asymptotic behaviors of the two functions.
As a result of this, the expression to represent the complexity for this algorithm would be t * n, however, since t is a constant, it should be omitted.
Hence, the time complexity is denoted as O(n).
Select the checkboxes under the Big O Notation Graph on to view graphs of common algorithm complexities.
As well, choose a complexity from the drop down menu on the right to view an explanation about it.
Definitions and Examples of Common Algorithm Complexities
Download Help Document