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 Big O notation here and the Big O cheat sheet here.

O(1) - Constant

It only takes a single step.

z = x + y

O(log n) - Logarithmic

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

x = 1
while x < 10:
  print(x)
  x *= 2

O(n) - Linear

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

for x in range(10):
  print(x)

O(n log n) - Quasilinear

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

for x in range(10):
  x = 1
  while x < 10:
    print(x)
    x *= 2

O(n2) - Quadratic

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

for x in range(10):
  for x in range(10):
    print(x)

O(2n) - Exponential

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

def fibonacci(x):
  if x <= 1:
    return x
  return fibonacci(x - 2) + fibonacci(x - 1)

O(n!) - Factorial

This is common in generating permutations.

def factorial(x):
  for i in range(x):
    factorial(x - 1)

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.

References

Related Articles