Page 563 - Computer science 868 Class 12
P. 563
If the number to be searched is not present in the array, then the loop executes n times. Thus, the worst case complexity
of linear search is O(N).
If the number to be searched is present in any other position, then the numbers of steps executed is greater than O(1)
and less than O(N) which is the average case complexity.
14.5 ANALYSIS OF COMPLEXITY OF COMMON ALGORITHMS
Bubble Sort: The algorithm for bubble sort is given below.
for(int i=0;i<n-1;i++)
{ for(int j=0;j<n-i-1;j++)
{ if(a[j]>a[j+1])
{ int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
The worst case complexity for an array of size n will be as follows:
st
In 1 pass through j loop: n-1 comparisons and n-1 swaps take place
nd
In 2 pass: n-2 comparisons and n-2 swaps take place
th
Similarly, in (n-1) pass through j loop: one comparison and one swap take place.
All together: c ((n-1) + (n-2) + ... + 1)
[where c = time for one comparison + one swap + check j loop condition + increment j and i loop is executed n-1 times]
if c1= time required to check loop condition + incrementing
Then total time:
c ((n-1) + (n-2) + ... + 1) + c1 (n-1)
= n(n-1)/2 + c1(n-1)
= c(n -n)/2+c1(n-1)
2
2
Here, n is the dominant term. Hence, complexity is Ọ(n ).
2
If bubble sort is performed on a list that is already sorted, it will finish in O(n) time which is its best case complexity.
The average and worst case complexity of a Bubble Sort algorithm is O(N ).
2
Selection Sort: The algorithm for selection sort is given below.
for(int i=0;i<size-1;i++)
{ s=a[i];
p=i;
for(int j=i+1;j<size;j++)
{ if(s<a[j])
{ s=a[j];
p=j;
}
}
t=a[i];
a[i]=a[p];
a[p]=t;
}
561
Computational Complexity and Big O Notation 561

