ASYMPTOTIC ANALYSIS SIMPLIFIED

#programming #discuss #100daysofcode #cpp

Why Analysis of Algorithms?

Suppose we can do a task using many methods, how do we choose a method that is efficient? We may see the efficiency of different methods. Efficiency maybe anything based on the context. Similarly in Computer Science, to solve a computational problem, there can be many algorithms. Now, How to select a efficient algorithm ? To select an efficient algorithm, we should know what is efficiency we refer in this case.

Discussing about different algorithms, we are interested in the following :

Correctness of the algorithm : Is the strategy or approach we are following is doing the intended task?
Correctness of the algorithm : Is the strategy or approach we are following is doing the intended task?
Optimal : To find the best ever algorithm possible

For ex : If a problem X can be solved using three algorithms which are A1, A2, A3 which take the time 10μs, 10ms and 100μs respectively. Can we say A1 is the efficient algorithm?

Which time are we considering?

If we consider system time, it is always dependent on system. We may also get system time different at different time frames. Hence we must consider some time complexity which is independent on the system.
Hence, while finding out time complexity, we shall focus on "Step Count". This refers to the count/frequency of fundamental / Primitive or prime operations involved in the program. This brings us to the topic Asymptotic analysis.

What is Asymptotic analysis?

Asymptotic analysis of an algorithm refers to defining the mathematical boundaries of the runtime performance. We can use this to define the best case, the worst case and the average case of an algorithm. This is always input bound, If there's no input required, we conclude that it can work in constant time.

In other words, it refers to computing the run-time of any operation of any algorithm. We can say that asymptotic analysis of any algorithm is a simple way to find the time taken for performing the algorithm in an abstract manner. Here, the time taken is proportional to the input size entered.

For example, if we are performing a linear search (Checking the key for each and every element, one-by-one ). If the input array size is 10, you require 10 units of time. If I increase the input 10 times, the time taken increase 10 times. Hence, here we are worried about how time taken changes on the increase on the input size.

Process for Asymptotic analysis?

Now, having learned what is asymptotic analysis, let's understand how do we proceed to do the analysis for an algorithm.

Step 1: So, once we choose the algorithm, first we need to do the step count. In step count, we count the number of times primitive or prime operations takes place. We express the time complexity as a function of the input size.
Step 2: After performing the step count, as we express the time complexity as a function of input size. Now we check the growth of the functions. We simply see how the function behaves when the size increases. This step includes little mathematics, calculus in precise. We have to know how to deal with growth of the functions.
Step 3: Now, we mainly focus on order of growth of significant terms of the time function. There are different ways / methods / notations. We simply compare the order of growth of the step count with some pre-defined, known functions. Ex: Logarithmic functions, Linear, Quadratic, Exponential etc.

This article would be continued further. So please follow me and stay connected. If you found this article useful, please let me know your feedback in the comments below. Also A reaction would always be appreciated.

Apart from this you can also connect with me on Twitter, LinkedIn, also GitHub. Thanks for reading this article.