Big O Notation in Data Structure

Big O notation in Data Structure – Big O notation is the most efficient tool to compare the efficiency of algorithms.

What is Big O notation?

Big O notation represents the upper bound of an algorithm and tells the asymptotic behaviour of a function, how fast a function f(n) grows when the input size n becomes large.

A function f(n) is of the order of g(n) if there exist constants c and n₀ such that f(n) <= c*g(n) where n is greater than n₀.

Note: here, the g(n) is the upper bound of the function f(n). Let’s understand it with an example.

Let’s say we have a function f(n) = 5n + 4, then how do we calculate the order of the function f(n)?

f(n) = 5n + 4
The upper bound of the function f(n) is n. 
so g(n) = n

let’s find the constants c and n₀

Using the definition, we can write the function f(n) like this.

f(n) <= c*g(n)
5n + 4 <= c*n for all n >= n0

let’s take c = 6 and n₀ = 4

then equation is

5n + 4 <= 6n for all n >= 4 
so the function f(n) = 5n + 4 is the order of n. and in mathematical terms.
5n+4 is O(n)

Let’s take another example

f(n) = 3n2 + 4n + 7
so, g(n) = n2
for values c = 5 and n0 = 6 function f(n) is 3n2 + 4n + 7 <= 5n2 for all n >= 6
so the function f(n) = 3n2 + 4n + 7 is order of n2
3n2 + 4n + 7 is O(n2)

Method to find the Big O notation of a function

To find the Big O notation of a function, we have some rules.

Rule First – Keep the fastest-growing term and discard the lower terms and constants.

For example, if the function f(n) = 3n² + 4n + 2, then the fastest-growing term is only 3n². So we will keep only 3n² and discard the lower terms 4n and constant 2 from the function f(n).

Rule Second – Ignore the coefficients from the equation. for example, we have function f(n) = 3n² then we remove the coefficients 3 from equation 3n².

Rule third – If the function f(n) is constant, then we say that f(n) is of order of 1. For example, we have a function f(n) = 4, then it’s an order of 1, because the function f(n) is constant.

Rule Fourth – The base of the logarithm is not important.

logan = logbn / logba

Both values for log a and b are constants. And we don’t consider constant values, so we ignore them. for example if the function f(n) = 8log₂n. Then we can say that function f(n) is the order of log n. 

Let’s take an example to understand how we find the Big O for a function.

Example 1

f(n) = 45
here the function f(n) is constant then it's an order of 1
f(n) is O(n)

Example 2

f(n) = 6n3 + 27log2n + 2n

Here we apply the rules

First, remove the lower terms and constants, then

f(n) = 6n3

Second, remove the coefficients, then

f(n) = n3

So the function f(n) is the order of n³.

f(n) is O(n3)

Example 3

f(n) = log2n + nlog10n
f(n) = nlog10n

So function f(n) is the order of n logn.
f(n) is O(n logn)

Bound of an algorithm

There are two bounds of the algorithm. One is tight, and the other is loosely bound. for a function f(n) there can be many functions g(n) such that f(n) is O(g(n)). let’s say we have a function f(n) = 5n² + 4n + 8 then the order of function f(n) is n². But it’s also the order of n³, n⁴ and nⁿ.

So the least upper bound of an algorithm is called the tight upper bound, and all other bounds are called loose upper bounds. So the tight upper bound of the function f(n) is n² and all other bounds are loose upper bounds.

Note: the loose upper bounds are not informative as the tight upper bound. So we only consider the tight upper bound of an algorithm.

Big O analysis of algorithms

We can also analyse the big O of an algorithm. So, to do this, first we need to express the running time of an algorithm as a function of input size n. Let’s say we have a function T(n) that represents the running time of an algorithm in terms of n. Then we need to find the big O of the function T(n).

Let’s say we have 4 algorithms A, B, C, and D, and the function T(n) represents the running time of an algorithm. Then, to analyse which algorithm is efficient, we need to calculate the big O for the function T(n) of all 4 algorithms.

So algorithm A is in the order of n³; similarly, algorithms B, C, and D are in the order of n², n, and n². as shown in Figure 2.

So algorithm C is efficient for our problem because it has the fastest running time.