We’ll discuss the analysis of algorithms, priori analysis, posteriori analysis, algorithm complexity – time complexity and space complexity, algorithm complexity of common operations, and asymptotic analysis.
Table of Contents
1. What is the Analysis of Algorithms?
If a problem has more than one solution, the technique used to decide which solution is best is known as algorithm analysis.
Analysis of algorithms refers to the task of determining how much computing time and storage space an algorithms requires. It helps us to determine which algorithm is most efficient in terms of time and space consumed.
Analysis is done on two parameters: time complexity and space complexity.
- Time Complexity – It means the time taken by an algorithm to solve a problem.
- Space Complexity means memory space required by an algorithm to solve a problem.
It can be done in two ways:
- Priori Analysis
- Posterior Analysis
1.1 What is Priori Analysis?
Priori Analysis is an analysis done before the execution. It is independent of CPU, OS, and system architecture and it provides uniform estimated values.
It is a software and hardware-independent analysis.
This type of analysis tells the approximate time and space complexity. It is the determination of the order of magnitude of a statement, meaning how many times a statement is executed.
1.2 What is Posteriori Analysis?
Posteriori Analysis is an analysis done after the execution. It is dependent on system architecture, CPU, OS, etc. It provides non-uniform exact values.
It is a software and hardware-dependent analysis.
This type of analysis tells the exact time and space complexity, meaning how much an algorithm takes time and space to solve a problem on the given system.
2. Difference between Priori and Posteriori Analysis
| Priori Analysis | Posteriori Analysis |
|---|---|
| software- and hardware-independent analysis. | software- and hardware-dependent analysis. |
| Theoretical analysis of an algorithm | Empirical analysis of an algorithm |
| It is constant for all the systems. | It keeps on changing from one system to other systems. |
| analysis tells the approximate time and space complexity | analysis tells the exact time and space complexity |
3. Worst, Average, and Best Cases
To analyze the given algorithms, we need to know with which inputs the algorithms take less time (performing well) and with which inputs the algorithms take a long time.
We have three cases to analyze an algorithm:
- Worst Case
- Average Case
- Best Case
3.1 Worst Case
In the worst-case analysis, we calculate upper bound on running time of an algorithm. This case causes the maximum number of operations to be executed.
3.2 Average Case
In average-case analysis, we take all possible inputs and calculate computing time for all of its inputs. Sum all the calculated values and divide the sum by the total number of inputs.
3.3 Best Case
In the best-case analysis, we calculate lower bound on running time of an algorithm. This case causes the minimum number of operations to be executed.
4. How to Compare Two Algorithms?
To compare algorithms, three steps are :
- Execution times? execution times are specific to a particular computer.
- Number of statements executed? the number of statements varies with the programming language as well as the style of the individual programmer.
- Ideal solution? running time of a given algorithm as a function of the input size n (i.e., f(n))
5. Algorithm Complexity
The efficiency of an algorithm depends upon the time and space used by the algorithm.
Space Complexity – How much memory is used?
Time Complexity – How many primitive operations are executed?
5.1 What is Time Complexity?
Time Complexity of an algorithm represents the amount of time required by the algorithm to solve a problem.
Computational Time is T(n) = c*n where c is the time taken to add 2 bits and n is the number of steps.
5.2 What is Space Complexity?
Space Complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle.
Space complexity S(P) of any algorithm P is S(P) = C + SP(I) where C is the fixed part and S(I) is the variable part which depends on instance characteristics I.
6. Algorithm Complexity of Common Operations
| Complexity | Operation |
|---|---|
| O(1) | Running a statement |
| O(1) | Value look-up on an array, object, variable |
| O(log n) | A loop that cuts the problem in half every iteration |
| O(n) | Looping through the values of an array |
| O(n2) | Double nested loops |
7. What is Asymptotic Analysis?
Asymptotic Analysis can be done by actually implementing both algorithms and running them on the same computer with different input values. Then the comparison is made in terms of time.
An algorithm that takes less time is considered better. But there are so many problems with this approach:
- It might be possible that for certain inputs first algorithm performs better than the second and for another set of inputs, the second algorithm performs better. So, the decision of choosing the best among them becomes difficult.
- With the change in the operating machine, the performance of the algorithm varies. On one machine first algorithm can work better and on another machine, the second works better. This is another problem associated with this approach
The above issues can be handled using asymptotic analysis techniques for analyzing algorithms. In asymptotic analysis, analysis of the algorithm is done in terms of input size. Actual running time is not computed, variation of time with input size is calculated.
FAQs
What is the difference between priori and posterior analysis?
Priori Analysis is an analysis done before the execution. It is a software and hardware-independent analysis. This type of analysis tells the approximate time and space complexity. It is the determination of the order of magnitude of a statement, meaning how many times a statement is executed.
Posteriori Analysis is an analysis done after the execution. It is a software and hardware-dependent analysis. This type of analysis tells the exact time and space complexity, meaning how much an algorithm takes time and space to solve a problem on the given system.
How do we estimate algorithm efficiency before execution?
Analysis is done on two parameters: time complexity and space complexity.
Time Complexity – It means the time taken by an algorithm to solve a problem.
Space Complexity means memory space required by an algorithm to solve a problem.
Why does posteriori analysis vary across different systems?
Posteriori Analysis is a software and hardware-dependent analysis means It is dependent on system architecture, CPU, OS, etc. This type of analysis tells the exact time and space complexity, meaning how much an algorithm takes time and space to solve a problem on the given system.