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 + yO(log n) - Logarithmic
The number of steps decreases in every step by some factor.
x = 1
while x < 10:
print(x)
x *= 2O(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 *= 2O(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.