# Algorithms Complexities

Performance analysis of an algorithm is done to understand how efficient that algorithm is compared to another algorithm that solves the same computational problem. Choosing efficient algorithms means computer programmers can write better and efficient programs.

A computer resource is memory and CPU time and performance analysis revolves around these two resources. Two ways to evaluate an algorithm is listed below.

1. Space requirement
2. Computation time

### Space Complexity

The space requirement is related to memory resource needed by the algorithm to solve a computational problem to completion. The program source code has many types of variables and their memory requirements are different. So, you can divide the space requirement into two parts.

Fixed Variables

The fixed part of the program are the instructions, simple variables, constants that does not need much memory and they do not change during execution. They are free from the characteristics of an instance of the computational problem.

Dynamic Variables

The variables depends on input size, pointers that refers to other variables dynamically, stack space for recursion are some example. This type of memory requirement changes with instance of the problem and depends on the instance characteristics. It is given by the following equation.

``````S(P) = c + SP
where
S(P) is space requirement
c is a constant
SP is the instance characteristics``````

Instance characteristics means that it cannot be determined unless the instance of a problem is running which is related to dynamic memory space. The input size usually has the control over instance of a computational problem.

### Time Complexity

The time complexity is the amount of time required to run the program to completion.It is given by following.

``````T(P) = compile time + run-time
P is the program.
T(P) is the time complexity of the program.``````

Program Execution in Steps

The computer executes a program in steps and each step has a time cost associated with it. It means that a step could be done in finite amount of time.See the table below.

You can count the number of steps an algorithm performed using this technique.

For example, consider the following example.

Note:-

S/e = steps per execution of a statement.

Frequency = The number of times a statement is executed.

The result of the step count is 2n + 3 which is a linear function. The performance analysis begins by counting the steps, but count the steps to execute is not the goal. The goal is to find a function that will describe the algorithm in terms of its input size. This function will tell you how the algorithm will perform for different input size and magnitude.