**Big-O** is a standard mathematical notation that shows how efficient an algorithm is in the *worst-case scenario* relative to its input size. To measure the efficiency of an algorithm, we need to consider two things:

**Time Complexity:**How much time does it take to run completely?**Space Complexity:**How much extra space does it require in the process?

Big-O notation captures the upper bound to show how much time or space an algorithm would require in the *worst case scenario* as the input size grows. It is usually written as:

$f(n) = O(inputSize)$

Time complexity is determined by taking two factors into account: the input size and the solution of the algorithm. Here’s a generic way to calculate the complexity:

- List down all the basic operations in the code
- Count the number of times each gets executed
- Sum all the counts to get an equation in terms of
*n*

Let’s look at the following code and see how we can calculate its complexity if the input size is equal to `n`

:

#include <iostream>using namespace std;int main() {int sum = 0;for (int i=0;i<5;i++){sum = sum+i;}cout << "Sum = " << sum;return 0;}

Let’s list down all the statements along with their execution count:

Operations |
Num of Executions |
---|---|

`int sum = 0` |
1 |

`for (int i=0;i<5;i++)` |
6 |

`sum = sum+i` |
5 |

`cout << "Sum = " << sum` |
1 |

`return 0` |
1 |

$$$$

$1+6+5+1+1$

Generalizing this notation in terms of input size (n) would form this expression:

$=>1+(n+1) + n + 1+1$

After simplifying the above expression, the final time complexity would be:

$2n +4$

To find Big-O notation, follow two steps:

- Discard the leading constants
- Ignore the lower order terms

After performing the above two steps on the time complexity that we just calculated, we can estimate the Big-O notation as:

$=> 2n+4$ $=> n+4$ $=> n$ $=> O(n)$

$$$$

Here’s a list of Big-O complexities sorted in ascending order:

Function |
Name |
Function |
Name |
---|---|---|---|

1. $O(1)$ | Constant | 7. $O(n^2)$ | Quadratic |

2. $O(log n)$ | Logarithmic | 8. O(n^3) | Cubic |

3. $O(log^2 n)$ | Log-square | 9. O(n^4) | Quartic |

4. $O(\sqrt n)$ | Root-n | 10. O(2^n) | Exponential |

5. $O(n)$ | Linear | 11. O(e^n) | Exponential |

6. $O(nlogn)$ | Linearithmic | 12. O(n!) | n-Factorial |

$$$$

Here is a rough plot of all the functions above to help you visualize the Big O time complexity to see where your algorithm lies in terms of efficiency.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS