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(n^{2}) | 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*

*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.