Algorithm is a set of computational procedures to solve a problem which has five main components –
Input – Algorithm must take some inputs
Output – It must be able to produce atleast one output
Definiteness – Each step of the algorithm must achieve a definite result.
Finiteness – Algorithm must end at finite number of steps.
Effectiveness – Algorithm must be effective to achieve the target it is designed for.
Why do we analyze an algorithm?
Algorithm analysis is performed to find a more efficient way to solve our problem. Let’s assume, you want to reach your office from your home. There may be many ways to reach your office from home. Then which way would you select? You’ll analyze all ways in accordance to your needs and on the basis of that you’ll select one way. To perform the same task, algorithm analysis is done.
How do we analyze an algorithms?
An algorithm is analyzed on the basis of two criteria:
1. Time complexity- How much time an algorithm takes in its completion. There are three main ways to analyze an algorithm on the basis of time:
- Best case analysis- This is the case when an algorithm can achieve its target in least time.
- Worst case analysis- Maximum time that an algorithm can take in achieving its target
- Average case analysis- This is general case, i.e. the time that an algorithm really take to achieve its target.
2. Space complexity- How much memory space is covered by an algorithm. Space complexity is measured by cost because more space consumption, more memory expense.
Here is an example of analysis of Insertion sort algorithm-
. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . .
