Time and Space Complexities of Popular Algorithms

Big-O Complexity

This is the algorithm’s worst-case complexity.

big_o_complexity
big_o_complexity

Time complexity – It is defined as the number of times a particular instruction has been executed rather than the total time taken by the entire program execution.

Space Complexity – It is defined as the total memory required by a program for its execution.

Types of Time Complexities

There are 3 types of time complexities that exist.

1] Best Time – It is the minimum time taken by the algorithm. Ex. if you are performing a linear search, if the element is present at the beginning of the array.

2] Average Time – It is averaged over all possible inputs. It’s calculated by dividing the total computing time for all inputs by the total number of inputs.

3] Worst Time – It is the maximum time taken by the algorithm. Ex. if you are performing a linear search, if the element is present at the last position of the array.

Notation for Time Complexities

1] Omega notation(Ω):- This notation describes the best-case scenario of the algorithm.

2] Theta notation:- This notation describes the average-case scenario of the algorithm.

3] Big-O notation (O): – This notation describes the worst-case scenario of the algorithm.

Some common Time complexity Notations

NotationMeaning
O(1)Constant Time
O(log n)Logarithmic Time
O(n)Linear Time
O(n long)Logarithmic-linear time
O(n^2)Quadratic Time
O(n^3)Cubic Time
O(2^n)Exponential Time
O(n!)Factorial Time

Time and Space Complexities of Sorting Algorithms

AlgorithmWorst Space ComplexityBest Time ComplexityAverage Time ComplexityWorst Time Complexity
Selection SortO(1)Ω(n^2)θ(n^2)O(n^2)
Bubble SortO(1)Ω(n)O(n^2)O(n^2)
Insertion SortO(1)Ω(n)θ(n^2)O(n^2)
Heap SortO(1)Ω(n log(n))θ(n log(n))O(n log(n))
Quick SortO(n)Ω(n log(n))θ(n log(n))O(n^2)
Merge Sorto(n)Ω(n log(n))θ(n log(n))O(n log(n))
Bucket SortO(n)Ω(n +k)θ(n +k)O(n^2)
Radix SortO(n+k)Ω(nk)θ(nk)O(nk)
Count SortO(k)Ω(n +k)θ(n +k)O(n +k)
Shell SortO(1)Ω(n log(n))θ(n log(n))O(n^2)
Tim SortO(n)Ω(n)θ(n log(n))O(n log (n))
Tree SortO(n)Ω(n log(n))θ(n log(n))O(n^2)
Cube SortO(n)Ω(n)θ(n log(n))O(n log(n))

Time and Space Complexities of Searching Algorithms

AlgorithmWorst Space ComplexityBest Time ComplexityAvarage Time ComplexityWorst Time Complexity
Linear SearchO(1)O(1)O(n)O(n)
Binary SearchO(1)O(1)O(log n)O(log n)
Jump SearchO(1)O(√n)O(√n)O(n)
Interpolation SearchO(1)O(log n)O(log n)O(n)
Fibonacci SearchO(1)O(log n)O(log n)O(n)

Download Link – Click Here

Leave a Reply

Your email address will not be published. Required fields are marked *

WhatsApp Icon Join For Job Alerts