# Big O Notation: Space and Time Complexity

## Introduction

Analysis of the runtime of the algorithm is performed in three ways they are Big O notation, Theta notation, and Omega notation. This article mainly explains Big O notation. It is the worst-case time complexity of the algorithm. It is calculated when huge inputs are given to the computer program. Big O notation is represented in terms of the given input to the algorithm. Generally, as O(N), where N is the size of the input.

## The mathematical definition of Big O notation is as follows:

The function f is said to be O(g) (read big-oh of g), where g and f are the functions from the set of natural numbers to itself if there is a constant c > 0 and a natural number n0 such that f(n) ≤ cg(n) for all n ≥ n0.

Big O notation gives the upper bound of the function as shown below:

f(n)= O(g(n)), f there exists a positive integer n0 and a positive constant c, such that f(n)≤c.g(n) ∀ n≥n0.

## Examples of Big O time complexity are as follows:

 S.No Algorithm Big O time complexity 1 Linear Search O(N) Runtime grows linearly in nature 2 Binary Search O(Log N) Runtime grows logarithmically to N 3 Selection Sort O(N2) Runtime is growing in a polynomial way. 4 Merge  Sort O(N log N) A super linear algorithm where Runtime grows directly with N. 5 Heap Sort O(N Log N) A super linear algorithm 6 Tower of Hanoi O(cN) Runtime grows even faster than polynomial algorithm based on N. 7 Factorial algorithm O(N!) Runtime grows very fast as compared to all other time complexity and is not considered to be efficient.

It is clearly explained in the below image:

## Conclusion

This article mainly explained Big O notation analysis in detail. Big O notation is the upper bound analysis of the computer program. It is calculated when huge input is given for the algorithm. It is considered to be the worst-case time complexity of the algorithm.

AlgorithmComputer ScienceC++ ProgrammingTime ComplexitySpace Complexity

### Blog | Board Infinity

At Board Infinity we have authors leading in their profession sharing their insights, ideas and inspiration. Here influential thinkers, creators, makers and doers are found in one place.