What Exactly is Time Complexity?
Have you ever been programming and had multiple algorithms to choose from? Which one did you choose? Was one faster? Why?
These questions are crucial in the field of computer science and dictate the speed at which websites and apps run. So how exactly do we find these answers? We use Time Complexity, a key concept that must be learnt if you wish to delve further into the world of computer science. In this article we will uncover the secrets behind super efficient algorithms and decode the notion of Time Complexity through Big-O notation and more.
Table of Contents
What is Time Complexity?
Let’s begin with an example to illustrate time complexity. You are at a supermarket with n aisles and want to buy croissants, but you have no idea where they are. What do you do?
Well, there are two options (algorithms):
- Go to each of the n aisles and check for croissants.
- Ask a shop assistant for help.
So which one would you choose? The second one right? Why check all n aisles when you could just ask the shop assistant and immediately go to the croissant aisle. While both options may take a similar amount of time for small values of n, as n increases, option two will undoubtedly dominate efficiency. This is the essence of Time Complexity.
Time Complexity essentially describes how computational effort scales with input size. In our example, option one exhibits a linear time complexity because the number of aisles to check increases linearly with input size, n. However, option two has a constant time complexity as regardless of the number of aisles, it will always require a constant amount of steps — asking the shop assistant.
Now how do we write this in a concise manner?
Well, we use Big-O, Big-Theta and Big-Omega notation, with Big-O being the most prevalent and scope of this article.
Big-O Notation
Big-O notation is used to represent the worst-case scenario of an algorithm. For instance, consider our earlier example; let’s choose option one and check every aisle one-by-one for croissants. While the croissants may conveniently be on aisle one, we must also be prepared for them to be on aisle n. This is the worst-case, which means the time complexity is O(n).
The table below displays the most commonly used time complexities.
Now that you’re familiar with various time complexities, let’s explore some examples and learn how to differentiate them.
Examples
Note: When calculating time complexities, always focus on the largest term as that is what will most affect the computational demand at larger inputs.
O(1) — Constant Time
print("This is constant time") #constant time, c
O(log n) — Logarithmic Time
def Number_of_Bits(n): #constant time, c1
i = 1 #constant time, c2
bits = 0 #constant time, c3
while i <= n: #executes floor(k)+1 times where 2^k=n so k=log(n)
i *= 2 #constant time, c4
bits += 1 #constant time, c5
return bits #constant time, c6
O(n) — Linear Time
def Sum_of_Integers_From_1_to_n(): #constant time, c1
sum = 0 #constant time, c2
for i in range(n+1): #loop executes n times
sum += i #constant time, c3
return sum #constant time, c4
O(nlog n) — Quasilinear Time
def Number_of_Bits_in_Array(arr): #constant time, c1
total_bits = 0 #constant time, c2
for i in arr: #executes n times(array input)
total_bits += Number_of_Bits(i) #calling O(logn) function from above
return total_bits #constant time, c3
O(n²) — Quadratic Time
def Create_Identity_Matrix(n): #constant time, c1
matrix = [[0] * n for i in range(n)] #loop+zeros executes n^2 times
for i in range(n): #loop executes n times
matrix[i][i] = 1 #constant time, c2
return matrix #constant time, c3
O(2^n) — Exponential Time
def fibonacci_recursive(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
#this recursion can be visualised as a binary tree, therefore O(2^n)
While this recursive Fibonacci program has a large time complexity, it can also be programmed iteratively resulting in a time complexity of O(n). This is a massive difference! Just look at our Time Complexity graph!
def fibonacci_iteratively(n): #constant time, c1
a = 0 #constant time, c2
b = 1 #constant time, c3
for i in range(n): #loop executes n times
a = b #constant time, c4
b = a + b #constant time, c5
return a #constant time, c6
O(n!) — Factorial Time
#generates n! permutations so must do n! computations
def generate_permutations(string):
if len(string) <= 1:
return string
first_character = string[0]
remaining_permutations = generate_permutations(string[1:])
permutations = set()
#the first character is positioned in every index of each permutation
for perm in remaining_permutations:
for i in range(len(perm) + 1):
new_perm = perm[:i] + first_character + perm[i:]
permutations.add(new_perm)
return permutations
We’ve done it! We have reached the end!
In this article, we have explored the most common time complexities and seen how they can vary between algorithms. In addition, I hope you have learnt how to calculate the time complexity of any given algorithm and its importance in the world of programming as observed in the Fibonacci example.
If you want to learn more about Time Complexity, specifically the Big-Oh, Big-Theta and Big-Omega Notation, please check out my article on these Three Important Time Complexity Notations!
