Big O Notation - Code Snippets to Understand Time Complexity

1) Constant Time - O(1)

The runtime of the algorithm is constant and does not depend on the input size.

2) Logarithmic Time - O(log n)

The runtime of the algorithm grows logarithmically with the input size.

3) Linear Time - O(n)

The runtime of the algorithm grows linearly with the input size.

4) Square Root Time - O(√n)

The runtime of the algorithm grows as the square root of the input size.

5) Loglinear Time - O(n log n)

The runtime of the algorithm combines linear time and logarithmic time.

6) Bilinear Time - O(n*m)

This is the time complexity of a nested loop where the inner loop runs m times for each iteration of the outer loop.

7) Quadratic Time - O(n²)

The runtime of the algorithm grows quadratically with the input size.

This typically happens when we do about n * n operations, such as a nested loop over the same array. Two separate passes over an array of size n are O(n) + O(n) = O(n), not O(n²).

8) Cubic Time - O(n³)

The runtime of the algorithm grows cubically with the input size.

9) Exponential Time - O(2ⁿ)

Exponential time complexity. The runtime of the algorithm grows exponentially with the input size.

This often appears in include/exclude decision trees, such as generating all subsets of n elements.

10) Factorial Time - O(n!)

The runtime of the algorithm grows factorially with the input size.

This often appears when generating all permutations of n distinct elements, where order matters.

---

NOTES

• Big O notation measures the growth rate of an algorithm as the input size increases, not its absolute speed.
• Just because an algorithm is O(1) does not mean that it is automatically fast.