What is performance analysis in Data Structure and an Algorithm?

Question

1. How performace analysis of an algorithm is done? 

• What do you mean by performace analysis?
• Which principles are used? 
• Why it is so? 
• Which parameters fall under this criteria? 

2. Space Complexity 

• what is space complexity? 
• Components of space complexity
• Examples

3. Time Complexity

• What is time complexity of an algorithm? 
• What are its components? 
• How do we measure time complexity of an an algorithm? 
• Examples

Answer 1

Why we do performance analysis?

Analysis of Algorithms-

• Two things keep in mind when thinking about an algorithm. First Analysis of algorithm and second design algorithm. Before design the algorithm, we should analyze the algorithm. Analysis of algorithms is the theoretical study of computer program performance and resource usage.  How fast an algorithm and Other resources such as memory, communication, etc.

• When developing a software, the developer needs to take care of its features like user-friendliness, correctness, simplicity, functionality, modularity, the robustness of software and security etc. Collection of features can be more important than performance. But Performance measures the line between feasible or infeasible. Another reason for studying performance is speed. In short, we can say performance is scale.

• In real-time requirement if a software is not good with a large scale of task or users, and taking too much time and memory, simply not feasible.

Performace Analysis

The performance of an algorithm can be analyzed based on following principles:

• Correctness

• Simplicity

• Optimality

• Readability

• Time complexity

• Space complexity

Correctness:

• Correctness of an algorithm helps in producing correct result. 

Simplicity:

• Simplicity of an algorithm helps in verifying the correctness of an algorithm. It helps in writing and modifying program easily.  

Optimality:

• Optimality helps in finding the best possible way to solve given problems.  

Readability:

• Readability makes the code readable.  

---

2. Space complexity

• Space complexity is the amount of space required to solve an algorithm.

• The space complexity of a computer program is the amount of memory space required to solve a problem as a function of size of the input.

S(p) =c+sp(i)

where c is a fixed space , which is independent of input and output . It is a constant.

where sp(i) is variable space and it depends on i.

Components of space complexity

There are three components of space complexity:

 Instruction or Code Space:

• This space holds the collected version of the program instructions.

 Data space:

• This space holds all the static data such as constant, variables and dynamic data such as growing structure.

 Environment Stack Space: 

• This space is used to store return address for the functions. So that,execution can begin again where they left earlier and it may also be used for parameters.

Example:Recursive function for summing a list of numbers:

float sum(float list[], int n)

{

if (n) return sum(list, n-1) +list(n-1) ;

}

S_sum(I)=S_sum(n) =6n

Space needed for recursive call of the above program

Type	Name	Number of bytes
parameter	list[]	2¹
parameter		2
return address(used internally )		2(unless for address)
total perrecursive call		6

---

2. Time complexity

•  Time complexity is the amount of time taken by an algorithm to execute a task.

• The time complexity of a program is the amount of time taken to solve a problem or function of size as inputs.

• If the time complexity of an algorithm is better, then the algorithm will carry out its work as fast as possible.

Components of Time Complexity

• The factors that affects the space complexity also affects time complexity.

• The time needed to execute an algorithm depends on several factors.

• Usually, it is difficult to find the exact time, so that we approximate the value.

• This approximate value can be found by assuming program ‘p’ by taking time is equal to the sum of compile time and run time.

• Compile time does not depend on the size of input hence, we will not consider compile-time and hence we will confirm ourselves to consider only the run time which depends on the size of the input.

o Let ‘t_p’ be the run time of the program.

o Again, we know that ‘ t_p’ depends on several factors. It is difficult to determine the exact value, hence we have to settle for less.

Approximately the ‘ t_p’ is given by,

‘t_p’(n) =C_a ADD(n) + C_s SUB(n) + C_​m​​MUL(n) +…… ..  

Here, n=Size of input

          C_a=Time needed for addition

          C_s=Time needed for subtraction

          C_m=Time needed for multiplication

Hence, we can say that the components of time complexity are operations(addition, subtraction, etc.) performed by processor.

In mathematically, time complexity is expressed as

   Time complexity t_p(h) =C+ t_p(n)

                   where, C is compile time

                                  t_p(n) is runtime.

For example:Recursion function for summing a list of numbers.

              float r_sum(float list[], int n)

              {

              if(n) return r_sum(list, n-1) +list(n-1) ;

              }

             S_sum(I) =S_sum(n) =6n

Speed needed for recursive call of above program.

Type	Name	Number of bytes
parameter	list[]	2
parameter		2
return address(used internally )		2(unless for address)
total perrecursive call		6

Measures of Time Complexity

 Average Case:

• The amount of time the algorithm takes on an average set of inputs.

 Worst Case:

• The amount of time the algorithm takes on the worst possible set of inputs.

 Best Case:

• The amount of time the algorithm takes on best set of inputs.

 Size of Input:

• The running time of a program can be expressed as a function of the size of the input. The size of the input is typically denoted as n and the running time of the algorithm as T(n). 

Time Complexity	Example
1	Find the 10th elements in an array.
logn	Binary Search
nlogn	Merge sort
n²	Selection sort
n³	Matrix multiplication

---