Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

Big o notation in data structures

YASH PAL, 11 May 202028 May 2024

Big O notation is the most efficient tool to compare the efficiency of algorithms. it represents the upper bound of an algorithm. it tells the asymptotic behavior of a function and how fast a function f(n) grows as input size n becomes large.

Big O notation – Definition

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

big o notation in data structures

Note: here the g(n) is the upper bound of 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 function f(n) is n. 
so g(n) = n

let’s find the constants c and n0

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 n0 = 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 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) = 3n2 + 4n + 2 then the fastest-growing term is only 3n2. so we will keep only 3n2 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) = 3n2 then we remove the coefficients 3 from equation 3n2.

Rule third

If the function f(n) is constant then we say that f(n) is the order of 1. For example we have function f(n) = 4 then it’s an order of 1. because 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) = 8log2n. 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 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 n3.
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 a loose 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) = 5n2 + 4n + 8 then the order of function f(n) is n2. but it’s also the order of n3, n4 and nn.

So the least upper bound of an algorithm is called the tight upper bound and all other bounds are called a loose upper bound.

So the tight upper bound of function f(n) is n2 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 analyze 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 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 analyze the algorithm that which one is efficient we need to calculate the big O for function T(n) of all 4 algorithms.

So algorithm A is in the order of n3, similarly, algorithms B, C, and D are in the order of n2, n, and n2. as shown in the above image.

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

Algorithms Tutorials Computer Science Tutorials Data Structures Tutorials Algorithmscomputer scienceData Structure

Post navigation

Previous post
Next post
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
  • Hackerrank Day 14 scope 30 days of code solution
©2025 Programming101 | WordPress Theme by SuperbThemes