Performance Analysis and Complexity

Performance Analysis:

• There are multiple algorithms to solve a problem. When we have more than one algorithm, we need to select one.

• Performance of an algorithm means predicting the resources which are required to an algorithm to perform its task.

• Performance analysis helps us to select the best algorithm to solve a problem.

• Performance analysis of an algorithm is the process of calculating space and time required by that algorithm.

Complexity:

• Complexity of an algorithm is a function f(n) which measures time and space used by an algorithm in terms of input size ‘n’.

• Algorithm complexity is commonly represented with the O(f) notation.

Complexity has two types:

     1. Time complexity

     2. Space complexity

Space Complexity:

Total amount of computer memory required by an algorithm to complete its execution is called as space complexity of that algorithm.

When we design an algorithm to solve a problem, it needs some computer memory to complete its execution. For any algorithm, memory is required for the following purposes:

1. To store program instructions.
2. To store constant values.
3. To store variable values.
4. And for few other things like function calls, jumping statements etc,.

Generally, when a program is under execution it uses the computer memory for THREE reasons. They are as follows....

Instruction Space: It is the amount of memory used to store compiled version of instructions.

Environmental Stack: It is the amount of memory used to store information of partially executed functions at the time of function call.

Data Space: It is the amount of memory used to store all the variables and constants.

Time Complexity:

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution.

Generally, the running time of an algorithm depends upon the following:

1. Whether it is running on Single processor machine or Multi processor Machine.

2. Whether it is a 32 bit machine or 64 bit machine.

3. Read and Write speed of the machine.

4. The amount of time required by an algorithm to perform Arithmetic operations, logical operations, return value, assignment operations and input data.

Constant Time Complexity:

If any program requires a fixed amount of time for all input values then its time complexity is said to be Constant Time Complexity.

Linear Time Complexity:

If the amount of time required by an algorithm is increased with the increase of input value then that time complexity is said to be Linear Time Complexity.