# Big-O Notation

The Big-O notation is about the performance or complexity of an algorithm. It describes the worst-case scenario, the execution time required, and the space used by an algorithm. You can get more explanation here and the cheat sheet here.

## O(1) - Constant

It only takes a single step.

## O(log n) - Logarithmic

The number of steps decreases in every step by some factor.

## O(n) - Linear

The running time increases linearly with the size of the input.

## O(n log n) - Quasilinear

The result of performing an O(log n) operation in n times.

## O(n^{2}) - Quadratic

The result of performing an O(n) operation in n times.

## O(2^{n}) - Exponential

This is common in situations when you traverse all the nodes in a binary tree.

## O(n!) - Factorial

This is common in generating permutations.

## Conclusion

Time complexity is to quantify the amount of time taken by an algorithm to run as a function of the length of the input. Space complexity is to quantify the amount of space or memory taken by an algorithm to run as a function of the length of the input.

See the example of linear time complexity above. The code is about printing numbers from 0 to 9. Even the time complexity is linear, but the space complexity is constant. Because we only need one variable to print each element, and the space for the variable doesn't change.