Analysis of Algorithms Made Easy

Introduction

This article presents a better approach to understand how to analyze algorithms. Moreover, we would like to understand what algorithms are and why are they important. This is the first article in the series Analysis of Algorithms Made Easy. I have dedicated a separate page for the same and you can get the list of all the articles in this series here.

Purpose of the article

In this article we will just try and understand the idea behind analyzing algorithms. It would be be more likely a Question and Answer article.

What is an algorithm ?

Answer: It’s a theoretical study of computer program’s performance and resource usage. But the focus is primarily on performance. There are many more factors which are more important than the performance. For e.g. : Correctness, Maintainability, Simplicity, Stability, Functionality, Modularity, Security, Scalability, User Friendliness and many more.

Why do we study algorithms and performance ?

Answer: Performance is one of the parameters which measures the line between feasible and in-feasible. e.g: If an algorithm is not fast enough , it might now be usable.
Also, if an algorithm consumes a lot of memory it might not be feasible to use.

Analyzing the classic problem of Sorting

Input: Given a sequence of numbers <a1, a2, a3, . . . , an>; .
Output: Permutation of numbers <a1′, a2′, a3′, . . . ., an’> such that a1′ <= a2′ <= a3′ <= . . . . <= an’ i.e. the numbers are monotonically increasing.

Solution

There are many solutions to this classic problem of sorting. In this article we will try and understand one of them called Insertion Sort

insertion

In this algorithm we maintain an invariant such that A[1…i-1] is sorted. We take the key as A[i], move left and compare each element with the key. In event of finding an element greater than the key we shift it one position to the right. In the event of finding an element smaller that the key at any location k (which is less than i), we re-place the element at k+1 with the key.

Below is the pseudo code for Insertion Sort.

isnertionpc

If you notice then the algorithm precisely picks the first element from the unsorted part of the array and inserts it in the right place in the sorted part. That is why it is called Insertion Sort.

Lets try to understand, what exactly is happening in the above pseudo code. We start with the following array:

array-step1

To begin with, we always assume that the first element is sorted.

step-1-is

We start with the second element and assign j with the index of the second element and assign j-1 to i i.e. i = 0, assign a[j] to key, so that key = 10 and keep decreasing i. i moves left and shifts each element one place to the right till we get a number smaller than key. We find that 6 is smaller than 10, and i gets the value 0. In the evidence of finding the number at index i, we insert the key at location i+1. This means 10 is inserted at index 1.

step2-is

This is the end of Iteration 1. Now we start the second iteration and increment j by 1, now j becomes 2 and points to the element 13 of the array, i becomes j-1 i.e. 1.
Following the same steps again will result in the following variant of the array.

step3-is

This concludes the Iteration 2. At the start of Iteration 3, j = 3 and i = j-1 = 2.

step4-is

On the same lines we can have the rest of the iterations.

Iteration 4: step5-is
Iteration 5: step6-is
Iteration 6: step7-is
Iteration 7: step8-is

And at the end of the final iteration we get the sorted array.

Running Time Calculation

How do we find out the running time of an algorithm?
What does it depend on?

Below are few factors which majorly influence the running time of the algorithm.

  • If the input is already sorted then insertion has nothing much to do.
  • Input size is an important factor, e.g. if we have to 10 elements at one time and 10 million elements at the other time then the second run will take more time.

Since the input size is contributing factor, we will always define running time in terms of input size.

Kinds of Analysis

  • Worst Case Analysis – It is defined as T(n) as the maximum time taken by any input of size n
  • Average Case Analysis – It is defined as T(n) as the expected time over all inputs of size n. We might make an assumption that all set of inputs are equally likely.
  • Best Case Analysis – We will mostly not analyze best case running time, because it tells us nothing about the permance of the algorithm.

What is Insertion Sort’s worst case time ?

Depends on the computer (computational abilities).
– we compare the algorithm’s relative speed by running them on similar machines or same machine.
– we compare the algorithm’s absolute speed by running them on different machines.

But we must know that the dependency on the hardware must not be a deciding factor until it is a very specific algorithm designed for a unique set of machines.

So the architects of algorithms found another way of judging algorithms and this is called Asymptotic Analysis.

Basic Idea behind asymptotic analysis

  • Ignore the machine dependent constants.
  • Look at the growth of the running time with changing input size.

Average case running time of Insertion Sort is T(n) = N*N when the elements are evenly distributed.
Worst case running time of Insertion Sort is T(n) = N*N, when the array is reversed sorted.

Code and Implementation

Is Insertion Sort fast?

Are there sorting techniques which can sort a list faster than insertion sort does?

The answer would be of course yes! Insertion sort is good but there is a room for better. This technique becomes highly in-effective if the list grows to a number more than 20 or 30. Also, it is not so effective when the input is already reverse sorted.

What Next and how do we improve Insertion Sort?
We can use Shell Sort which internally uses Insertion Sort to deliver results in more efficient manner. Please visit the article on Shell Sort to learn more about it.

Conclusion

We learned to sort an array using insertion sort and found it to be a better aorting technique if the array is not sorted. Also, if the array is too large then the insertion sort takes more time because it has to traverse through the whole array.

You can always visit Wiki to know the history or some other details of Insertion Sort.
Stay connected and stay Subscribed

  • Raghavender

    line no: 16 i should be greater than or equal to 0 i..e, while (i >= 0 && a[i] > key)