This topic is super trendy in interviews, so you have to know it if you are looking for a job

There’s not only one way to solve a problem, but not all of them are the best. Every solution is not capable of efficiently using our resources. Therefore, we need to find the best, most efficient solution to a problem before taking action.

In programming, we can’t leave the mechanism of finding the best solution, the best algorithm to guesswork. We need a clear standard to evaluate their efficiency. This is where the concepts of time and space complexity steps in. They help us determine the algorithm’s efficiency based on the required resources.

In this post, we are going to talk about the concepts of time and space complexity and how we can use them to select the most efficient algorithm for a given task. And of course, this is where notations like O(n), O(logn) that may have baffled you while learning algorithms come from.

---

Efficiency of Algorithms

We measure an algorithm’s efficiency using the time and space (memory) it takes for execution. Time is important because we need our programs to run as fast as possible to deliver the results quickly. Space is important because machines have only a limited amount of space to spare for programs.

The best algorithm is the one that completes its execution in the least amount of time using the least amount of space. But often, in reality, algorithms have to tradeoff between saving space or time.

That’s why the best algorithm for a given task is not something that’s fixed in stone. The best algorithm depends on our requirements. If we need our algorithm to run as fast as possible despite the memory usage, we can pick the most time-efficient algorithm as the best algorithm and vice versa.

And if we need to save both time and space, we can settle for an algorithm that uses average amounts of time and space.

---

Space Complexity

Space complexity of an algorithm is the amount of space it uses for execution in relation to the size of the input.

n = int(input())

nums = []
for i in range(1, n+1):
    nums.append(i*i)

In this example, the length of the list we create depends on the input value we provide for n.

Let’s say adding a single integer to the list takes c space and other initial operations, including creating a new list, takes d space. Then, we can create an equation for the space taken by the above algorithm like this.

when n       -> c*n + d
when n = 10  -> c*10 + d
when n = 100 -> c*100 + d

The value calculated by this equation is the space the algorithm needs to complete execution. The values of the constants c and d are outside of the control of the algorithm and depend on factors such as programming language, hardware specifications, etc.

However, we don’t need the exact value this equation calculates to talk about the space complexity of an algorithm. Instead, we use the highest order of the variable n as a representative of the space complexity.

For example, the above algorithm has a space complexity in the order of n. If another algorithm has the equation c*n2 + d*n + e for space it needs, we say it has an order of n2 space complexity.

---

Time Complexity

Time complexity is the number of elementary operations an algorithm performs in relation to the input size. Here, we count the number of operations, instead of time itself, based on the assumption that each operation takes a fixed amount of time to complete.

If we look at the previous algorithm again, it performs n number of operations (n iterations of the loop) to complete its execution.

If we construct a similar equation for time complexity as we did before, it also takes the shape of c*n + d, with c as the fixed time taken for each loop iteration and d as the fixed time taken for other initial operations.

Therefore, the time complexity of this algorithm is also in the order of n.

---

Asymptotic Analysis

As you saw in these examples, we can’t compare one algorithm to another using exact values because they depend on the tools we use and underlying hardware. In fact, if we calculated time and space values for two instances of running the same algorithm on the same system, there would be differences in the values we get due to subtle changes in the system environment.

Therefore, we use Asymptotic Analysis to compare the space and time complexity of two algorithms. It analyzes the performance of an algorithm against the input size. It evaluates how the performance changes as the input size increases. This type of analysis doesn’t need actual values for space or time taken by the algorithm for comparison.

---

Best, Worst, and Average Cases

Usually, in asymptotic analysis, we consider three cases when analyzing an algorithm: best, worst, and average.

To understand each case, let’s take an example of a linear search algorithm. We use a simple for loop to search if a given integer k is present in a list named nums of size n.

def linear_search(nums, n, k):
    for i in range(n):
        if k == nums[i]:
            return i
    return -1

Let’s consider what are the best, worst, and average case scenarios for this algorithm in terms of time complexity (We can talk about these three scenarios in terms of space complexity too).

Best Case

We consider the combination of inputs that allows the algorithm to complete its execution in the minimum amount of time as the best-case scenario in terms of time complexity. The execution time in this case acts as a lower bound to the time complexity of the algorithm.

In linear search, the best-case scenario occurs when k is stored at the 0th index of the list. In this case, the algorithm can complete execution after only one iteration of the for loop.

nums = [1, 2, 3, 4, 5, 6]
n = 6
k = 1

Worst Case

Worst case scenario occurs when the combination of inputs that takes the maximum amount of time for completion is passed to the algorithm. The execution time of the worst case acts as an upper bound to the time complexity of the algorithm.

In linear search, the worst case occurs when k is not present in the list. This takes the algorithm n+1 iterations to figure out that the number is not in the list.

nums = [1, 2, 3, 4, 5, 6]
n = 6
k = 7

Average Case

To find the average case, we get the sum of running times of the algorithm for every possible input combination and take their average.

In linear search, the number of iterations the algorithm takes to complete execution follows this pattern.

When k is stored at the 0th index  -> 1 iteration
When k is stored at the 1st index  -> 2 iterations
When k is stored at the 2nd index  -> 3 iterations
When k is stored at the 3rd index  -> 4 iterations
:                                  :
When k is stored at the nth index  -> n iterations
When k is not in the list          -> n+1 iterations

So, we can calculate the average running time of the algorithm this way.

---

Asymptotic Notation

Asymptotic notation is a mathematical notation used to represent the time and space complexity of algorithms in asymptotic analysis. We mainly use three asymptotic notations to represent the best, worst, and average cases of algorithms.

Ω (Big-Omega) Notation

Ω notation denotes an asymptotic lower bound of a function. In other words, it says that the function should output at least the respective big-omega value for a given input.

For a function g(n), we can define the set of functions denoted by Ω(g(n)) as follows.

Ω(g(n)) = {
  f(n): there exist positive constants c and n0 such that
    0 <= c*g(n) <= f(n) for all n >= n0
}

It’s a mouthful. But let’s break down this definition with an example and try to understand what it means.

First, let’s take the function g(n) = n2.

Now, the big-omega of g(n) represents the set of functions that satisfies the condition 0 <= c*g(n) <= f(n) for all n >= n0 when c and n0 are positive constants.

Let’s consider the function f(n) = 2n2 + 4

For c = 1 and n0 = 1, 0 <= c*g(n) <= f(n) for all n >= n0
Therefore, f(n) = Ω(g(n))

Now, if we consider f(n) = 3n + 5, we can’t find values for constants c and n0 that satisfy the above conditions. Therefore, f(n) = 3n +5 doesn’t belong to big-omega of g(n).

In time and space complexity, Ω notation is used to represent the best-case scenario of an algorithm. It can provide lower bounds to time and space complexity.

O (Big-O) Notation

O notation denotes an asymptotic upper bound of a function. In other words, the function should output at most the respective big-O value for a given input.

For a function g(n), the definition of the set O(g(n)) is as follows.

O(g(n)) = { 
  f(n): there exist positive constants c and n0 such that
    0 <= f(n) <= c*g(n) for all n >= n0
}

Again, let’s use an example to understand this definition.

g(n) = n2
f(n) = 2n2 + 4
For c = 5 and n0 = 1, 0 <= f(n) <= c*g(n) for all n >= n0
Therefore, f(n) = O(g(n)

And if we consider f(n) = n3+2, it doesn’t belong to O(g(n)) because no combinations of values for c and n0 satisfies the required condition.

We use O notation to represent the worst-case time and space complexity of an algorithm.

Θ (Big-Theta) Notation

Θ notation denotes an upper and a lower bound of a function. Therefore, it defines both at most and at least boundaries for the values the function can take for a given input.

The standard definition of the Θ notation is as follows.

Θ(g(n)) = {
    f(n): there exist positive constants c1, c2 and n0 such
        that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0
}

Let’s use an example to understand this definition with the g(n) and f(n) functions we used so far.

g(n) = n2
f(n) = 2n2 + 4
For n0 = 1, c0 = 1, and c1 = 5, 0 <= c0*g(n) <= f(n) <= c1*g(n) for all n >= n0
Therefore, f(n) = Θ(g(n))

Big-theta notation is used to define the average case time and space complexity of an algorithm.

---

Time and Space Complexity of Popular Algorithms

Selection Sort

The selection sort algorithm is used to sort a list of items.

1. It iterates through the list once and finds the minimum item and puts it at the starting index of the list.
2. Then, in the next iteration, it finds the second minimum item and puts it in the second place.
3. This pattern continues until all the items in the list are sorted.

def selection_sort(nums, n):
    """
    nums: the list of numbers to sort
    n: the length of the list
    """
    for i in range(n-1):

        min_index = i
        #search the unsorted indexes for the next minimum number
        for j in range(i+1, n):
            if (nums[j] < nums[min_index] ):
                min_index = j
        #Swap the next minimum number with the earliest unsorted number
        nums[i], nums[min_index] = nums[min_index], nums[i]

Time Complexity

Let’s consider the best, worst, and average-case time complexities of this algorithm.

The best-case occurs when the passed list of numbers is already in sorted order. However, the selection sort algorithm still has to complete all the iteration steps because it doesn’t have a mechanism to know whether the list is already sorted or not.

If the algorithm completes in p number of steps,

We can see that p has an order of n2. Therefore, the best case time complexity of the selection sort is Ω(n2).

Selection sort behaves the same way for every other input including the worst case scenario. So, its worst-case and average-case time complexities are O(n2) and Θ(n2).

Space Complexity

Selection sort doesn’t store additional data in the memory. It only modifies the original list. Therefore, it has a constant space complexity of O(1).

Bubble Sort

The bubble sort algorithm compares adjacent items in the list and swaps them if the first item is smaller than the second item. It continues this operation until no swaps are performed while iterating through the list (i.e., the list is sorted).

For example, [22, 12] are two adjacent items in the list, bubble sort swaps them and changes the order to [12, 22].

def bubble_sort(nums, n):
    for i in range(n-1):
        swapped = False
        for j in range(n-i-1):
            if (nums[j] > nums[j+1]):
                #Swap the adjacent numbers to keep them in ascending order
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = True

        if not swapped:
            break

Time Complexity

In the best case when the passed list is already sorted, the algorithm performs n-1 operations, which is in the order of n. Therefore, its best-case time complexity is Ω(n).

In the worst case, when the items in the list are in descending order, the algorithm performs a number of operations in the order of n2. Therefore, bubble sort has a worst-case time complexity of O(n2).

The average time complexity of the algorithm is also Θ(n2).

Space Complexity

Similar to selection sort, bubble sort has a constant space complexity of O(1).

Insertion Sort

Insertion sort algorithm follows these steps to sort a list of items.

1. Iterate through the array starting from the 0th index.
2. Check if the current item is smaller than its predecessor.
3. If yes, compare the current item to the item before the predecessor.
4. Continue this until an item smaller or equal to the current item is found.
5. Place the current item next to the smaller item by moving the greater items one position up.

def insertion_sort(nums, n):
    for i in range(1, n):
        current = nums[i]
        
        #Check the previous items to find where current item fits in the sorting order
        j = i-1
        while j >= 0 and nums[j] > current:
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = current

Time Complexity

In the best case, the insertion sort algorithm takes only n operations because the list is already sorted. Therefore, it has Ω(n) best case time complexity.

In the worst case, the algorithm takes

number of operations to complete, which is in the order of n2. So the worst case time complexity is O(n2).

Space Complexity

Again, since this algorithm modifies the list in place without using additional memory, it has a space complexity of O(1).

Merge Sort

Merge sort divides the given list into shorter lists and sorts them before combining them together to create a fully sorted list. The steps involved in the algorithm are as follows.

1. Divide the list into two halves by its middle point.
2. Merge sort the first and second halves of the list separately.
3. Merge the two sorted halves to create the final sorted list.

As you might have guessed, merge sort is a recursive algorithm that calls the mergeSort function again and again on halved lists until the initial list is separated into singular items. Then, it merges these items back in the sorted order.

def merge(arr, left, right):

    i = j = k = 0

    #Compare the elements in the two lists starting from the first items
    #Add the smallest item to the merged list 
    #Continue this until all items of one list are added
    while i < len(left) and j < len(right):
        if (left[i] < right[j]):
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    #Check if there are more items in left list and merge them in order
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    #Check if there are more items in right list and merge them in order
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1


def merge_sort(arr, n):
    if (n > 1):
        mid = n//2
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left, len(left))
        merge_sort(right, len(right))

        #Merge left and right lists in sorted order
        merge(arr, left, right)

Time Complexity

Merge sort has time complexities with the same order in best, worst, and average case scenarios. Let’s see how we can find this order of the algorithm.

• Merge sort algorithm divides a list of n items into two continuously until there are n number of lists with single items.
• If n = 2x, this takes x number of divisions by 2 to get to the base level. So it creates x number of levels, each level containing arrays of size n/2, n/4, …, n/2^x-1, n/2^x. We can calculate the value of x using logarithms. It is log2n.
• If 2^x+1 > n > 2^x, it takes x+1 number of divisions by 2 to get to the base level. This results in creating x+1 levels. We can round up the value of log2n+1 to find the value of x+1.
• In each level, the merge sort algorithm iterates once through each item in separated lists while merging left and right lists together. Because there n items in total, each level takes n number of operations to complete the merge.
• Since there are, at most, logn+1 levels, the total number of operations the algorithm carries out is n*( logn+1). It’s in the order of n*logn.

Therefore, the best, worst, and average time complexity of merge sort is respectively, Ω(n*logn), O(n*logn), and Θ(n*logn).

Space Complexity

Merge sort uses additional n space to store the items in the divided arrays. Therefore, it has a space complexity of Ω(n), O(n), and Θ(n) in best, worst, and average cases.

Linear Search

Linear search algorithm goes through each item in the list to find out if a certain item is stored in it.

def linear_search(nums, n, k):
    for i in range(n):
        if k == nums[i]:
            return i
    return -1

Time Complexity

This algorithm iterates through each item in the list once in the worst case. Therefore, it has a worst case time complexity of O(n). In the best case, search completes with one search iteration and has a time complexity of O(1).

Space Complexity

Linear search doesn’t use additional space to store items. Therefore, has a space complexity of O(1).

Binary Search

Binary search algorithm is used to find a given item in a sorted list of items. It uses a different mechanism to linear search to complete the search faster.

1. Find the middle item of the list and compare it to the given item k.
2. If the middle item is equal to k, the algorithm completes.
3. If k is smaller than the middle item, perform binary search on the array to the left of the middle item.
4. If k is larger than the middle item, perform binary search on the array to the right of the middle item.
5. Continue this operation recursively until k is found or the fact that k is not in the list is certain.

def binary_search(nums, left, right, k):
    if (left <= right):
        mid = left + (right - left)//2

        #Check if the mid item is equal to k
        if (nums[mid] == k):
            return mid

        #If k is smaller than the middle item, check the left half of the list
        elif nums[mid] > k:
            return binary_search(nums, left, mid-1, k)
        
        #If k is lerger than the middle item, check the right half of the list
        else:
            return binary_search(nums, mid+1, right, k)
    
    return -1

Time Complexity

Binary search, similar to what you saw in the merge sort algorithm, uses a divide and conquer approach to solve the problem. It divides the array into two and searches for the given item on the relevant side of the array. In the worst case, the algorithm divides the array logn+1 times at most. Therefore, it has a worst case time complexity of O(logn).

In the best case, the middle item of the passed list has to be the searched item. Therefore, as it completes in constant time, the best case time complexity is Ω(1).

Space Complexity

The best case space complexity of binary search is Ω(1).

The worst case space complexity depends on the implementation. With a recursive implementation as we have done, binary search has a space complexity of O(logn) due to storing additional data on mid, left, and right values for each recursive call. An iterative implementation can reduce the complexity to O(1).

---

Summary of Algorithm Complexities

	Space			Time
	Best	Avg	Worst	Best	Avg	Worst
Selection sort	Ω(n²)	Θ(n2)	O(n²)	Ω(1)	Θ(1)	O(1)
Bubble sort	Ω(n)	Θ(n2)	O(n²)	Ω(1)	Θ(1)	O(1)
Insertion sort	Ω(n)	Θ(n2)	O(n²)	Ω(1)	Θ(1)	O(1)
Merge sort	Ω(nlogn)	Θ(nlogn)	O(nlogn)	Ω(n)	Θ(n)	O(n)
Linear search	Ω(n)	Θ(n)	O(n)	Ω(1)	Θ(1)	O(1)
Binary search	Ω(1)	Θ(logn)	O(logn)	Ω(1)	Θ(1)	O(1)

If you’ve been confused by time and space complexity of algorithms before, I hope this post helped you resolve this confusion at least to some extent.

Thank you for reading.

Source: livecodestream