What is Analysis of Algorithm
The analysis is a process of evaluating the efficiency of an algorithm.
Analysis of algorithms is the process or procedure of searching the computational complexity of algorithms. This is way to find the storage, amount of time, or other resources required to execute them.
Algorithmic analysis ( Analysis of Algorithm ) is an significant part of computational complexity theory, which provides theoretical estimation for the necessary resources of algorithms to solve a special computational problem.
There are two basic parameters on the basis of which we can analyze algorithms:
- Space Complexity
- Time Complexity
Space Complexity
The complexity of space can be understood as the amount of space required by the algorithm to run until it is complete. Space complexity is defined as the process of defining a formula for predicting the need for memory space for successful execution of the algorithm. The memory space is usually considered the primary memory.
For an algorithm, space is required for the following purposes:
- To store constant values
- To store program instructions
- To footprints the function calls, jumping statements, etc.
- To store variable values
Auxiliary space
The extra space is called an auxiliary space, except for the input size by the algorithm. The auxiliary space and the space used by the input.
so,
"Space complexity = Auxiliary space + Input size."Time Complexity
The time complexity of algorithm is the amount of time needed to complete execution.
The time complexity of the algorithm is represented by the large O notation. Here, the larger O notation is asymptomatic signaling to represent time complexity. The difficulty of time is mainly calculated by counting the number of steps or part to Complete the implementation.
Types Of Analysis
Generally, we perform three types of analysis, which is as follows:
- Worst-case time complexity: For "n" input size, a worst time complexity can be defined as a highest time required by the algorithm to finish its execution. Thus, it is nothing but a function defined through the maximum number of steps performed.
- Average case time complexity: For "n" input sizes, the average-case time complexity can be defined as the average amount of time required by the algorithm to execute. Thus, it is nothing but a function defined by the average number of steps performed on an instance with an input size of n.
- Best case time complexity: For the "n" input size, the best-case time complexity can be specified by the algorithm as a minimum time needed to finish their execution. Thus, it is nothing but a function defined by the minimum steps performed on an instance with an input size of n.
How to analyze algorithm efficiency
The algorithm can be analyzed in two levels, that is, the first is before the algorithm is created, and the second is after the algorithm is created. The following are two analyzes of the algorithm:
- Priori Analysis: Here, preliminary analysis is the theoretical analysis of an algorithm that is showed off before the algorithm is implemented. Before applying the algorithm to the processor speed, Various factors can be considered, which has no effect on the implementation part.
- Posterior Analysis: The posterior analysis is a practical analysis of an algorithm. Applying the algorithm to any programming language achieves practical analysis. This analysis basically evaluates how much time and space is taken by the algorithm.
0 Comments