The Big-O notation is about the performance or time complexity of an algorithm. It describes the worst-case scenario, the execution time required, and the space used by an algorithm. You can get the more explanation here and the cheat sheet here.
O(1) - Constant Time
It only takes a single step.
z = x + y
O(log n) - Logarithmic Time
The number of steps decreases in every step by some factor.
x = 1 while x < 10: print(x) x *= 2
O(n) - Linear Time
The running time increases linearly with the size of the input.
for x in range(10): print(x)
O(n log n) - Quasilinear Time
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 Time
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 Time
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 Time
This is common in generating permutations.
def factorial(x): for i in range(x): factorial(x - 1)