Algorithm
Analysis in DSA
Algorithm
Analysis
Algorithm Analysis means
to calculate time and space required by the algorithm to execute. A simple
example to calculate time and space requirements for a simple algorithm :
function
sum(int a, int b){
  int s = 0; -------
1 unit
  s = a + b; -------
1 unit for adding a and b, and 1 unit for assignment,total 2 units
  display "sum : "+s;  --1 unit for displaying
}Â Â
Time
Complexity or Time requirement
Let's suppose that each statement
of the algorithm takes one unit of time. There are three statements in the
given algorithm, but one statement consists of two operations add and
assignment, so, total time take by the algorithm to execute is 1+ (1+1) +1 = 4
units of time. We can say that the time requirement of given algorithm is Order
of 1, O (1).
Space
Complexity or Space Requirement
Here, in the given
algorithm three variables: a, b, and s are declared. Each variable takes 1 unit
of memory space, so total space (memory) requirement is 1 + 1 + 1 = 3 units. It
can be said that space requirement is of order 1, O (1). If the time or space
requirement for an algorithm is some constant like: 1, 5, 40 etc. then we say
the time or space requirement is order of 1, O (1).
function
sum(int n,int[] Arr) {
int
s = 0;
int
i;Â Â Â ------- 1 + 1 = 2 units
for(i=0;i<n;i++){Â Â ------- 1+ (n+1)+n = (2n + 2) units; we can
ignore smaller terms.
If
n = 4 then the condition of the for loop will run: when i=0; i = 1; i = 2; i =
3;i =4; so, total number of times condition checking runs is n + 1.
  s = s + Arr[i]; --n units (0, 1, 2, 3 if n=4) for displaying
}Â Â Â
 display s;  ---
1 unit of time
}Â Â Â Â Â Â Â Â Â
The time complexity of
the given algorithm which adds all the numbers of the given array of size n is
2 + (2n+2) + n + 1 = (3n
+ 5) Units.
The degree of polynomial
2n+3 is 1, so the algorithm is order of n, O(n).
function
sumArrays(int [] arra, int[] arrb){
int
s = 0,i,j; ------- 1 + 1 + 1 = 3 units
for(i=0;i<n;i++){Â Â ------- n+1 units (ignoring i=0; and i++)
 for(j=0;j<n;j++){ -------n * n+1 units
    s = arra[i] + arrb[j];  --n *n units for displaying
 }Â
}Â Â Â
 display s;  ---
1 unit of time
}Â Â Â
The time complexity of
the given algorithm sumArrays, is:
3 + (n+1) + (n * (n+1)) +
(n * n) + 1 = 2n2+2n+5
2n2+2n+5 polynomial is of
degree 2, so, the algorithm is of order of n2, O(n2)
Other related courses:
Introduction to Data Structure and Algorithm Overview of Syllabus
Linked List with Types and Examples
Stack and Queue with ExamplesÂ
Sorting and It's Types with Examples
