Asymptotic Analysis

Introduction

This article Data Structures and Algorithms – Asymptotic Analysis presents a better approach to understand how to analyze algorithms. Moreover, we would like to understand what algorithms are and why they are important. In this article we will just try and understand the idea behind analyzing algorithms.

On the other hand if you are interested in watching a video for this article, you can subscribe our Youtube Channel.


Question: What are algorithms and their analysis?

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 etc.

Question: Why do we study algorithms and performance?

Answer: Performance is one of the parameters which will measure the line between feasible and in-feasible. For 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: A sequence of numbers.
Output: Permutation of numbers 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. 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.

Know more about the Insertion Sort.

Running Time Calculations

Question: How do we find out the running time of an algorithm and what does it depend on?

Answer: 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 obviously 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 performance of the algorithm.

Question: What is Insertion Sort’s worst case time?

Answer: It actually 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 to fairly judge the efficiency of algorithms, 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.

Best Case: The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., proportional to N). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

Worst Case: The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases each iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (proportional to N2).

Average Case: The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quick sort; indeed, good quick sort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as sub problems; the exact threshold must be determined experimentally and depends on the machine.

Question: Is Insertion Sort fast and are there sorting techniques which can sort a list faster than insertion sort does?

Answer: 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.