What is Runtime Analysis of Algorithms
In computer science, the analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.
In simple terms, to measure the efficiency of a given algorithm.
Why do we need to learn this ?
Algorithm analysis is the science of knowing how complex an algorithm is in terms of time and space.
The analysis of an algorithm can help us understand it better and can suggest informed improvements.
Analyzing an algorithm is to discover its characteristics in order to evaluate its suitability for various applications.
For example : Take a scenario of buying a vehicle.
Let’s say we are going to buy a bike and we visit a showroom. We like a particular model and we see for a salesman. The first question that we ask to the salesman is, how the bike performs?. So here we are trying to analyse the product here, which is a bike.The salesmen gives us an answer considering three scenarios.
Salesmen say that the bike gives a mileage of 30 in Normal traffic, it gives a mileage of 25 in Heavy traffic and last it gives a mileage of 38 on Highways.
So if you look at the salesmen answer from a computer science point of view, the salesmen is trying to analyse the bike in three different scenarios i.e the Average case(normal traffic), Worst case(heavy traffic), and the Best case(on highways).
Algorithm are measured/analyse in term of Notations. There are three types of notation in which a algorithm can be analysed.
Types of Notations :
1. Omega(Ω) Notation :
The notation Ω(n) is the formal way to express the lower bound of an algorithm’s running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.
For eg : let’s say we are sorting 1000 number, so the minimum time required to sort 1000 numbers is “10 secs”. In omega notation, those 1000 numbers cannot be sorted in less than 10 secs. It can be 11 secs, 12 secs but not 9 or 8 secs.
2. Big-o(O) Notation :
The big-o is the formal way to express the upper bound of an algorithm’s running time. It measures the worst case time complexity or the maximum amount of time an algorithm can possibly take to complete.
For eg : let’s say we are sorting 1000 number again, so the maximum time required to sort 1000 numbers is “50 secs”. In big-o notation, those 1000 numbers can be sorted in less than 50 secs. It can be 48 secs, 46 secs but not 51 or 52 secs.
3. Theta(Θ) Notation :
The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior. For any given input, the running time of a given algorithm will “on an average” be equal to given time.
For eg : let’s take again the example of sorting 1000 numbers, for the first time the algo takes 10 secs, if we sort it again it take 11 secs, and again if we sort for the 3rd time it takes 7 secs.
So the theta notation will say that the algorithm “on an average” take 9 secs to execute the method.
