Need of Algorithm
1. To understand the basic idea of the problem.
2. To find an approach to solve the problem.
3. To improve the efficiency of existing techniques.
4. To understand the basic principles of designing the algorithms.
5. To compare the performance of the algorithm with respect to other techniques.
6. It is the best method of description without describing the implementation detail.
7. The Algorithm gives a clear description of requirements and goal of the problem to the designer.
8. A good design can produce a good solution.
9. To understand the flow of the problem.
10. To measure the behavior (or performance) of the methods in all cases (best cases, worst cases, average cases)
11. With the help of an algorithm, we can also identify the resources (memory, input-output) cycles required by the algorithm.
12. With the help of algorithm, we convert art into a science.
13. To understand the principle of designing.
14. We can measure and analyze the complexity (time and space) of the problems concerning input size without implementing and running it; it will reduce the cost of design.
Analysis of algorithm
The analysis is a process of estimating the efficiency of an algorithm. There are two fundamental parameters based on which we can analysis the algorithm:
- Space Complexity: The space complexity can be understood as the amount of space required by an algorithm to run to completion.
- Time Complexity: Time complexity is a function of input size n that refers to the amount of time needed by an algorithm to run to completion.
Let’s understand it with an example.
Suppose there is a problem to solve in Computer Science, and in general, we solve a program by writing a program. If you want to write a program in some programming language like C, then before writing a program, it is necessary to write a blueprint in an informal language.
Or in other words, you should describe what you want to include in your code in an English-like language for it to be more readable and understandable before implementing it, which is nothing but the concept of Algorithm.
In general, if there is a problem P1, then it may have many solutions, such that each of these solutions is regarded as an algorithm. So, there may be many algorithms such as A1, A2, A3, …, An.
Before you implement any algorithm as a program, it is better to find out which among these algorithms are good in terms of time and memory.
It would be best to analyze every algorithm in terms of Time that relates to which one could execute faster and Memory corresponding to which one will take less memory.
So, the Design and Analysis of Algorithm talks about how to design various algorithms and how to analyze them. After designing and analyzing, choose the best algorithm that takes the least time and the least memory and then implement it as a program in C.
In this course, we will be focusing more on time rather than space because time is instead a more limiting parameter in terms of the hardware. It is not easy to take a computer and change its speed. So, if we are running an algorithm on a particular platform, we are more or less stuck with the performance that platform can give us in terms of speed.
However, on the other hand, memory is relatively more flexible. We can increase the memory as when required by simply adding a memory card. So, we will focus on time than that of the space.
The running time is measured in terms of a particular piece of hardware, not a robust measure. When we run the same algorithm on a different computer or use different programming languages, we will encounter that the same algorithm takes a different time.
Generally, we make three types of analysis, which is as follows:
- Worst-case time complexity: For ‘n‘ input size, the worst-case time complexity can be defined as the maximum amount of time needed by an algorithm to complete its execution. Thus, it is nothing but a function defined by the maximum number of steps performed on an instance having an input size of n.
- Average case time complexity: For ‘n‘ input size, the average-case time complexity can be defined as the average amount of time needed by an algorithm to complete its execution. Thus, it is nothing but a function defined by the average number of steps performed on an instance having an input size of n.
- Best case time complexity: For ‘n‘ input size, the best-case time complexity can be defined as the minimum amount of time needed by an algorithm to complete its execution. Thus, it is nothing but a function defined by the minimum number of steps performed on an instance having an input size of n.