Big O Notation
What is Big O Notation?
Big O Notation is used to express the complexityof an algorithm
Describes thescalabilityof an algorithm as it'sorder(O), referred to in Computer Science asBig O Notation
Named after the German mathematicianEdmund Landau
Has two simple rules
Remove all terms except the one with the largest factor or exponent
Remove any constants
There are several classifications used in Big O Notation, ranging from fast and efficient to slow and inefficient. These are all covered below
Constant
O(1), read as Big-O One, describes an algorithm that takes constant time, that is, requires the same number of instructions to be executed, regardless of the size of the input data
For example, to calculate the length of a string ‘s’ the following code could be used:
totalLength = len(s)
No matter how long the string is, it will always take the same number of instructions to find the length
Linear
O(n), read as Big-O n, describes an algorithm that takes linear time, that is, as the input size increases, the number of instructions to be executed grows proportionally
For example, a linear search of 1000 items will take 10 times longer to search than an array of 100 items
Implementing linear time requires use of iteration i.e. for loops and while loops
In the example of sumNumbers1, a basic (for i = 1 to n) loop is used
Below is an example of an algorithm that uses multiple for loops
function loopx = inputfor i = 1 to xprint(x)next ia = 0for j = 1 to xa = a + 1next jprint(a)b = 1for k = 1 to xb = b + 1next kprint(b)endfunctionWhen the user inputs a value of x, each loop will run x times, performing varied instructions in each loop
The total number of instructions executed in this algorithm are as follows:
+1 for (x = input)
+x for the first for loop
+1 for (a = 0)
+x for the second for loop
+1 for (output a)
+1 for (b =1)
+x for the third for loop
+1 for (output b)
The total number of instructions executed would therefore be: 3x + 5
As x increases the total number of instructions executed also increases as shown in the table below
Linear Time: Number of Instructions Executed
x | 3x | 5 | 3x + 5 |
|---|---|---|---|
1 | 3 | 5 | 8 |
10 | 30 | 5 | 35 |
100 | 300 | 5 | 305 |
10,000 | 30,000 | 5 | 30,005 |
1,000,000 | 3,000,000 | 5 | 3,000,005 |
The constant term (5) contributes less and less to the overall time complexity as x increases. 3x is the significant contributing term and causes the overall time complexity to grow linearly in a straight line as x increases
Polynomial
O(n2), read as Big-O n-squared, describes an algorithm that takes squared time to complete. This means the performance is proportional to the square of the number of data inputs
For example, a bubble sort is a polynomial time complexity algorithm. n passes are made, and for each pass n comparisons are made hence n*n or O(n2)
Implementing polynomial time requires the use of nested iteration i.e. for loops or while loops, where each loop executes n times
An example of a polynomial algorithm is shown below:
function timesTablex = 12for i = 1 to xfor j = 1 to xprint(i, “ x “, j, “ = “, i*j)next jnext ifor k = 1 to xprint(k)next kprint(“Hello World!”)endfunctionThe above algorithm outputs the times tables from the 1 times table to the 12 times table. An arbitrary for loop (for k = 1 to 10) and output (print(“Hello World!”)) has been added for demonstration purposes as shown below
The total number of instructions executed by this algorithm are as follows:
+1 for (x = 12)
+x * x for the nested for loop
+x for the non-nested for loop
+1 for (print(“Hello World!”))
The total number of instructions executed would therefore be: x*x + x + 2 or, x2 + x + 2
As x increases the total number of instructions executed also increases as shown in the table below
Polynomial Time: Number of Instructions Executed
x | x2 | 2 | x2 + x + 2 |
|---|---|---|---|
1 | 1 | 2 | 4 |
10 | 100 | 2 | 112 |
100 | 10,000 | 2 | 10,102 |
10,000 | 100,000,000 | 2 | 100,010,002 |
1,000,000 | 1,000,000,000,000 | 2 | 1,000,001,000,002 |
The constant term (2) and linear term (x) contribute very little as x increases, making x2 the significant contributing term
To put this algorithm into perspective, assuming it took one second per instruction, printing up to the 1,000,000 times table would take roughly 32,000 years
Loops can be nested any number of times. In the example above, there are two loops nested. Each loop nested increases the polynomial time as shown below. Regardless of the number of loops nested, all are still referred to as polynomial time!
Big-O of Nested Loops
Number of loops nested | Big-O time |
|---|---|
2 | O(n2) |
3 | O(n3) |
4 | O(n4) |
5 | O(n5) |
6 | O(n6) |
Below is an example of a six nested algorithm. Note that the algorithm does nothing useful except demonstrate this nesting
for a = 1 to nfor b = 1 to nfor c = 1 to nfor d = 1 to nfor e = 1 to nfor f = 1 to nnext fnext enext dnext cnext bnext aExponential
Exponential time, read as Big-O 2-to-the-n, describes an algorithm that takes double the time to execute for each additional data input value. The number of instructions executed becomes very large, very quickly for each input value
Few everyday algorithms use exponential time due to its sheer inefficiency. Some problems however can only be solved in exponential time
Exponential time: Number of Instructions Executed
x | 2x |
|---|---|
1 | 2 |
10 | 1024 |
100 | 1,267,650,600,228,229,401,496,703,205,376 |
Exam Tip
You do not need to know any specific examples of exponential time complexity algorithms, but you do need to know how these algorithms compare to other time complexities.
Logarithmic
Logarithmic time, read as Big-O log-n, describes an algorithm that takes very little time as the size of the input grows larger
Logarithmic time in computer science is usually measured in base 2. A logarithm is the value the base must be raised to to equal another number, for example:
23 = 8, log2(8) = 3, i.e. to get to the value 8, 2 must be raised to the power of 3
A binary search is an example of logarithmic time complexity. Doubling the size of the input data has very little effect on the overall number of instructions executed by the algorithm, as shown below:
Logarithmic Time: Number of Instructions Executed
x | log2(x) |
|---|---|
1 (20) | |
8 (23) | 3 |
1,024 (210) | 10 |
1,048,576 (220) | 20 |
1,073,741,824 (230) | 30 |
As shown above, increasing the number of input values to over one billion did very little to the number of instructions taken to complete the algorithm
Comparison of Complexity
All algorithms have a best case, average case and worst case complexities.
These are defined as the best possible outcome, the average outcome and the worst possible outcome in terms of the number of instructions required to complete the algorithm
Best case complexity is where the algorithm performs most efficiently such as a linear search or binary search finding the correct item on the first element O(1), or a bubble sort being supplied with an already sorted list O(n). A bubble sort must always make at least one pass, hence O(n)
Average case complexity is where the algorithm performs neither at its best or worst on any given data. A linear search may find the item in the middle of the list and therefore have a Big-O notation of O(n/2), or a bubble sort sorting only half a list O(n2 / 2)
Worst case complexity is where an algorithm is at its least efficient such as a linear search finding the item in the last position, or not at all O(n), or a bubble sort sorting a reversed list O(n2), i.e. a list whose items are ordered highest to lowest
Big-O notation is almost always measured by the worst case performance of an algorithm. This allows programmers to accurately select appropriate algorithms for problems and have a guaranteed minimum performance level
The graphical representation of constant, linear, polynomial, exponential and logarithmic times is shown below
Big-O Time Complexity Graph
Figure 1: Graph of Time Complexity for Big-O Notation Functions
From the graph, exponential time (2n) grows the quickest and therefore is the most inefficient form of algorithm, followed by polynomial time (n2), linear time (n), logarithmic time (logn) and finally constant time (1)
Further time complexities exist such as factorial time (n!) which performs worse than exponential time and linear-logarithmic time (nlogn) which sits between polynomial and linear time. Merge sort is an example of an algorithm that uses O(nlogn) time complexity
The Big-O time complexity of an algorithm can be derived by inspecting its component parts
It is important to know that when determining an algorithm's Big-O that only the dominant factor is used.
This means the time complexity that contributes the most to the algorithm is used to describe the algorithm. For example:
3x2 + 4x + 5, which describes three nested loops, four standard loops and five statements is described as O(n2)
x2 is the dominating factor. As the input size grows x2 contributes proportionally more than the other factors
Coefficients are also removed from the Big-O notation. The 3 in 3x2 acts as a multiplicative value whose contribution becomes smaller and smaller as the size of the input increases.
For an arbitrarily large value such as 10100, which is 10 with one hundred 0’s after it, multiplying this number by 3 will have little contribution to the overall time complexity. 3 is therefore dropped from the overall time complexity
Exam Tip
The most likely type of Big-O calculation question you will face in an exam is deriving a constant, linear or polynomial time complexity
A very challenging question may ask to derive a logarithmic time complexity which will require familiarity with logarithmic algorithms from your course to recognise them
The simplest way of deriving time complexity is to count the number of loops and nested loops in an algorithm.
function sumNumbers1(n)sum = 0for i = 1 to nsum = sum + nnext ireturn sumendfunctionIn the example above for sumNumbers1, a single for loop is present. As loops are O(n) and single statements are O(1), the overall Big-O notation is O(n), linear time, as the loop dominates constant time
function sumNumbers2(n)sum = n * (n+1)/2return sumendfunctionIn the example above for sumNumbers2, a single statement is present with no loops. Statements are O(1) therefore making the overall Big-O notation O(1), constant time
function loopx = inputfor i = 1 to xprint(x)next ia = 0for j = 1 to xa = a + 1next jprint(a)b = 1for k = 1 to xb = b + 1next kprint(b)endfunctionIn the example above for function loop, there are three loops present 3*O(n) and five statements 5*O(1). As the input size grows, the quantity of loops or statements becomes negligible, meaning coefficients eventually become factored out or removed. This leaves O(n) and O(1). As O(n) dominates O(1), the overall Big-O notation of this algorithm becomes O(n), linear time
function timesTablex = 12for i = 1 to xfor j = 1 to xprint(i, “ x “, j, “ = “, i*j)next jnext ifor k = 1 to xprint(k)next kprint(“Hello World!”)endfunctionIn the example above for function timesTable, there is a single nesting of two loops O(n2), a single loop O(n) and a single statement O(1). As polynomial time dominates linear and constant time and that no coefficients are involved, the overall Big-O notation is O(n2)
Worked Example
Dexter is leading a programming team who are creating a computer program that will simulate an accident and emergency room to train hospital staff.
Two of Dexter's programmers have developed different solutions to one part of the problem. Table 3.1 shows the Big O time complexity for each solution, where n = the number of data items.
Solution A | Solution B | |
|---|---|---|
Time | O(n) | O(n) |
Space | O(kn) (where k > 1) | O(log n) |
Table 3.1
Explain, with reference to the Big O complexities of each solution, which solution you would suggest Dexter chooses.
[4]
I would recommend solution B [1]. As both have the same time complexity we would need to look at both algorithms' space complexity [1]. A’s space does not scale well [1] when the number of items is increased whereas B’s space does scale well [1].
Remember to relate your answer to the context of the question to achieve marks.
