Last lesson you have learnt about Hashing. This lesson introduces the Big O Notation, as another important topic. Big O Notation is widely used for calculating the performance of the algorithm/program.
Learning outcome
On successful completion of this lesson, you would be able to define Big-O notation, describe properties of notation and types of Big-O functions and analysis of performance of an algorithm using Big-O functions. Define Big-O notation Properties of Big-O Types of Big-O functions Analysis performance of an algorithm using Big -O
9.1 What is Big O Notation?
Big O notation is used in Computer Science to describe the performance or complexity of an
algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. Big O helps us determine which algorithm could be best suited for solving a problem. Big O stands for Order (Ordnung). It was first used by a German number theorist Paul Bachman to represent an “order of”. It is denoted symbolically as O(n), where n is an integer which represents size of the input data set.
9.2 properties of Big-O
Let us look at several properties of Big –O. As Big O involves with numbers, let's start by considering the positive numbers. There is a notion of order: when x is lower than y we write as
1 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
X ≤ Y. We can add and multiply numbers, and the order relation respect these operations:
X ≤ Y, Z ≤ W ⟹ X + Z ≤ Y + W, XZ ≤ YW.
Similar to this, we can have several properties of Big-O.
1) Scaling – this feature tells us that, when there is a scalar in the function f(n),Big-of f(.) can ignore the scale. It has been presented in the following Lemma 01
Lemma 01
For all constant factors c > 0, the function c f(n) is O(f(n)), or in shorthand notation cf is O(f).
The proof: c f(n) < (c + ε)f(n) holds for all n > 0 and ε > 0. Then Constant factors are ignored. Only the powers and functions of n should be exploited It is this ignoring of constant factors that motivates for such a notation! In particular, f is O(f).
2) Trasitivity: If function h(n) grows at most as fast as g(n), which grows at most as fast as f(n), then h(n) grows at most as fast as f(n).
Examples: If h ∈ O(g) and g ∈ O(n2 ), then h ∈ O(n2 ).
3) Rule of Sums
If g1 ∈ O(f1) and g2 ∈ O(f2), then g1 + g2 ∈ O(max{f1, f2}).
This can be proved as follows.
2 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
Informally, the rule of sums says that, the sum of functions grows as its fastest-growing term. Therefore
If g ∈ O(f) and h ∈ O(f), then g + h ∈ O(f).
If g ∈ O(f), then g + f ∈ O(f). If g(n) = a0 + a1n + . . . + ak n k (a polynomial of degree k), then g(n) ∈ O(n k ).
Examples:
If h ∈ O(n) and g ∈ O(n 2 ), then g + h ∈ O(n 2 )
4) Rule of Products If g1 ∈ O(f1) and g2 ∈ O(f2), then g1g2 ∈ O(f1f2). This can be proved as follows.
3 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
Informal meaning of the rule of products can be presented as follows.
The product of upper bounds of functions gives an upper bound for the product of the functions. Therefore, • If g ∈ O(f) and h ∈ O(f), then gh ∈ O(f 2 ). • If g ∈ O(f) and h ∈ O(f k ), then gh ∈ O(f k+1). • If g ∈ O(f) and h(n) is a given function, then gh ∈ O(f h)
Examples: If h ∈ O(n) and g ∈ O(n 2 ), then gh ∈ O(n 3 ).
9.3 Types of Big – O and Analysis of Performance of an algorithm
Based on the value of n, different Big O functions/notations can be introduced.
1) O(1) – This describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set. I.e. irrespective of changing the size of the input, time stays the same. Let look at the following Java program.
public static boolean isArrayOver100(String[] args) {
if (args.length > 100)
return true;
return false;
Here, in this program, we take an array of string as an input and check whether the length
of the array is greater than 100. If yes, it returns true otherwise it returns false. Thus, no
matter how big the array is, we do only one check i.e. whether the length is greater than
100. Hence the program or algorithm will always execute in the same time. This is also
called as a constant time algorithm.
4 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
2) O(n) – This function indicates that, as you increase the size of an input, the time taken to complete operations scales linearly with that size. Let us see how this happens. Consider the following Java program.
public static boolean contains(String[] args, String value)
{ for (int i = 0; i < args.length; i++) { if (args[i] == value) return true; } return false; }
The example above demonstrates how Big O favours the worst-case performance scenario;
a matching string could be found during any iteration of the for loop and the function
would return ‘True’ early, but Big O notation will always assume the upper limit where
the algorithm will perform the maximum number of iteration.
3) O(n2) – This represents an algorithm whose performance is directly proportional to the
square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(n3), O(n4) etc…
Consider the following program.
public static boolean containsDuplicates(String[] args) { for (int i = 0; i < args.length; i++) { for (int j = 0; j < args.length; j++) { if (i == j) break; if (args[i] == args[j]) return true; } }
5 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
return false; } It you carefully look at this algorithm, you can see that it goes through the same array twice in two iteration, i.e. in nested iterations. In the worst case, the FOR loop needs to be executed n*n times. Thus, it makes O(n2) performance of the algorithm.
4) Logarithms in Big O – O(log n)
Binary search is a technique used to search in sorted data sets. You will learn this under searching algorithms. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element (i.e. the middle value) it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.
This type of algorithm is described as O(log n). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets.
Consider the following function for binarysearch.
public static int binarySearch(int[] toSearch, int key) { int fromIndex = 0; int toIndex = toSearch.length - 1;
6 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
while (fromIndex < toIndex) {
int midIndex = (toIndex - fromIndex / 2) + fromIndex; int midValue = toSearch[midIndex];
Thus, the efficiency of the algorithm, in other words time or space required to execute this algorithm can be stated as O(log n) where n is the number of input data. This also called as logarithmic time algorithms.
9.4 Big-O complexity Analysis
Figure 1 compares the complexity of several big O notations. You can see that a performance of an algorithm in which performance function lie in the RED or ORANGE areas are terrible i.e. its computational efficiency is very low. Any performance function lie in GREEN area is amazing. Hence we you are designing an algorithm you need to try to stick either to YELLOW or GREEN areas.
7 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
Figure 1: complexity analysis of Big-O functions.
Activity 9.1
Consider the following program. Compute the performance of the algorithm.
// A function to implement bubble sort
void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); }
Activity 9.1- Answer : performance is O(n2)
8 Big – O Notations ITE 2142 – Data Structures & Algorithms Week 09
Summary During this lesson you learnt about Big O notation. You also saw that different Big O notations can be introduced based on the nature of the algorithm implemented. You also learnt that how to compute the performance of an algorithm in their worst case execution. Moreover, you got to know about algorithms which are good in their performance and also algorithms which are worst.
