In this week’s newsletter, I want to briefly introduce you to time and space complexity and then follow it up with complexity analysis of the most popular sorting and searching algorithms.

Let’s get started.

What is Time and Space Complexity?

When you’re trying to solve a problem or building something new, It’s a best practice to first do a step by step analysis of how you’re solving a problem and the possible outcomes of it. It can be as simple as adding two numbers or swapping two variables, or a complex problem such as transferring petabytes of data between two systems. 

This step by step solution we write as an answer to a problem is what we call an algorithm.

Time Complexity is the total amount of time taken by an algorithm to run with respect to the input. It is a representation to understand how the time to execute our algorithm changes as the input varies.

For example, an algorithm to add two numbers takes two inputs and returns its sum. If we assume that the algorithm takes 1 unit of time to complete for a given input a and b, the time doesn't change no matter how we vary the inputs a and b because the algorithm just adds and returns the result, nothing varies here. 

Hence we can say that this algorithm executes at a "constant time" or the time complexity is constant.

On the other hand, an algorithm that calculates the sum of a series of numbers can take a variable amount of time depending on the count of numbers in that series. 

To better express the time taken by our algorithm for an input, we need to employ a generalized notation. Time complexity can be expressed in the following three terms - 

• Big O - represents the minimum time an algorithm takes to execute. An algorithm can't take lower than the big-O time of its execution for any input. 

• Big Omega - represents the maximum time an algorithm takes to execute. An algorithm can't execute higher than the big-Omega time of execution for any input.

• Big Theta - represents a tight-bound on the execution time of an algorithm.

Now that we have a brief understanding of the Complexity notations, let us apply these on some of the popular algorithms out there - Sorting and Searching.

Learning that fits your life: anytime, anywhere learning with Udemy, starting from as low as ₹499. Know more

Summarizing Complexity Analysis of Sorting Algorithms

Sorting is the method of arranging a series of values in some order. There are two types of sorting algorithms out there, based on how they achieve this -

1. Internal Sorting algorithms - which try to sort the values in place, without using any buffer memory

2. External Sorting algorithms - which use a temporary buffer memory to place values while trying to sort them in order

The following are some of the important sorting algorithms, let’s briefly summarize them -

Selection Sort

• swaps elements to their actual places based on the comparison criteria

• two pointers run throughout the given dataset and the inner loop pointers seek through the entire dataset once for every single move of the outer loop pointer. 

• For every seek, the inner loop pointer looks for the element in the loop which is smaller than the element of the outer loop pointer and then swaps the elements once the seek is complete.

• Since the inner pointer runs through all the elements for every pass of the outer pointer, the algorithm takes O(n(n-1)/2) which is equivalent to O(n²) time, for all cases.

• This is the most basic and least efficient sorting algorithm

Insertion Sort

• This algorithm relies on the movement of the elements from their original places to their actual places

• Two pointers i,j which run on the dataset. For one iteration of i; j loops from the pointer i, until the occurrence of an element smaller than the current element of i encountered "in reverse" and moves the element to a relatively "smaller" position in the set. Then the element at j is replaced with the current element at i.

• Works comparatively less time because the loop doesn't necessarily run till the beginning of the loop at all times, hence the worst case is equivalent to O(n²) time, while an optimal case somewhere lesser than it.

Quick Sort

• most efficient internal sorting technique

• uses a "divide and conquer" approach for its sorting

• the algorithm breaks the input dataset into working subsets based on a criteria and then recursively applies the same approach on the resultant subsets, while performing sorting on these subsets

• Based on a median element named “pivot”, we start from both the ends of the dataset and swap the elements such that all the elements in the left side of the chosen "pivot" are lesser than it and all the elements on the right side of the pivot are greater than it.

• Once the left and right pointers which are running from the opposite side run across each other, divide the dataset into smaller subsets based on the index where these indices collide. 

• This repeats until both the pointers point to the same index, meaning all the elements are sorted.

• For every iteration of the dataset the subject dataset on which the algorithm works on is almost divided to half, Hence the time taken for this algorithm is logarithmic, and it's an average of O(NLogN) for any given dataset.

Merge Sort

• another Divide and Conquer algorithm similar to Quick Sort

• Divides the given input set into pieces as small as individual elements, and then recursively merges these partitioned pieces - while placing the elements in these subsets into proper order.

• The division happens first, till the individual elements are reached, and then the "merge" happens from the leaves till the original set is reconstructed. 

• We merge them using two temp arrays to hold these sub arrays.

• Roughly takes O(NlogN) time. But the space required is O(n), since we make use of temp space to hold these sub arrays

Heap Sort

• Works on the basis of the construction of a heap data structure, which is an array visualized to be a nearly complete binary tree.

• We create a sorted array out of an unsorted array by repetitively creating a Max Heap from the array and then replacing the root node which happens to be the maximum element of the set in each iteration.

• Since the operations assume that we're operating on a tree, the time taken for operations are logarithmic in nature. Total complexity for the Heap Sort is O(NlogN), time is constant.

Summarizing Complexity Analysis of Searching Algorithms

• For a given set A containing N elements, we need to find the index at which the target element E occurs in the set. This is called searching. We have two approaches here - Linear search, Binary search.

• A Simple Linear Searching algorithm seeks through every element of the array in a linear fashion and then compares with the target element. If the element is found then the algorithm stops there.

• In this algorithm, the time taken for the lookup grows linearly as the input set A grows in size. Hence the worst case complexity of this search is O(N) where N is the number of elements in the set.

• In Binary Search, we know that the set is already sorted. Hence, for any given iteration, we examine only "half" of the given input set for the target element and if it is not found, we'll further reduce the lookup to smaller subsets, until we run out of the elements.

• For every iteration (or recursion), the algorithm works on exactly "half" of the initial subset that the algorithm works at the beginning. Hence the algorithm takes logarithmic time, which is O(logN)

Learn, practice, succeed (and save) with courses from S$16.98 in Udemy. Click here to grab the deal.