Welcome! In my previous post, I wrote about the use of different notations for Asymptotic (Algorithmic) Analysis. Today, let’s discuss how the analysis is done.
Why is it called Asymptotic Analysis?
In every case, for a given function, f(n), we define a function g(n) which approximates f(n) at higher values of n. Thus, g(n) is a curve, approximating f(n) at higher values of n. Such a curve is called an Asymptotic Curve. For this reason, the Algorithm Analysis is called Asymptotic Analysis.
Rates of Growth
The Rate at which the running time increases as a function of input is called rate of growth. In case of a total time of execution
C0n2 + C1 + (C2 + C3)n, since the smaller elements and constants are insignificant for large values of n, the actual rate of grown is considered to be
This, rate of growth:
Here is a chart with commonly used Rates of Growth:
Reading the index of the 1200 page beauty that is CLRS, I realized going in that completing all of it in a given period is not a practical goal. I read the preface first, to see how the authors want us to proceed. Reading it, I realized that I need some basic Algorithmic knowledge beforehand. I needed to learn about the Algorithm Analysis and the different Notations we use.
Why Algorithm Analysis?
Let’s talk about the Sorting problem. There are multiple ways to solve it. There’s Quick-sort, insertion sort, bubble sort, merge sort. Why do we need more than one methods to get the exact same end result?
The Answer to this lies behind the use of these sorting techniques. While all our sorting techniques to the same thing, when we use bubble-sort on an array of 1000 numbers, we discover how much extra time it takes, as compared to quick sort. This is but a small example, in case we have an even bigger set of data, the sorting time will increase exponentially, which will lead to not only an unpleasant User Experience (users hate lag!) but also increase the capacity of our program.
How to compare Algorithms?
Let’s first think of a couple different ways to compare algorithms,
- Execution Time: Not a good measure since the execution time would vary not only with the input, but also different computers.
- Number of statements executed: This is also an inefficient method, less number of statements do not necessarily mean faster algorithm. The same algorithm implemented in python might be smaller than in C. This does not mean that it is faster.
- Amount of time taken to design: While it may be considered for a moment that a well thought out algorithm should perform better, there is no guarantee that an algorithm designed quickly can not be effective or faster.
So, I bought my domain and server space back in June 2016, since I wanted to get hands-on experience with writing API calls for Android and learning backend development. Excited as I was for a teenager with his own website (which, was an empty welcome page for quite a while), I started reading and learning how stuff works around the Internet.
Slowly learning and developing my skill-set, I learnt that I can very easily start my own blog using WordPress and the likes. So I created a sub-domain, and then, there came the big question!