Page 562 - Computer science 868 Class 12
P. 562
Let us take this simple program as an example.
int s1=0; Let time taken be t1
int s2=0; Let time taken be t2
for(int i=1;i<=n;i++)
{ s1=s1+i;} Let time taken be t3
for(int j=1;i<=n;j++)
{ for(int k=1;k<=n;k++)
{ s2=s2+i*j;} Let execution time be t4
}
System.out.println(s1); Let execution time be t5
System.out.println(s2); Let execution time be t6
Time taken to execute single loop = n*t3
Time taken to execute nested loop = n*n*t4
2
Total time taken = t1 + t2 + t3*n + t4*n + t5 + t6
Time taken t1, t2, t5 and t6 is constant and is independent of input size. So, constants are ignored while calculating
complexity.
2
The term which has maximum impact on the above algorithm’s performance is t4*n . So, while calculating complexity
we ignore the rest of the terms and consider the term which has maximum impact on the algorithm’s performance. This
term which dominates the algorithm the most is called the dominant term and is only included in the Big O notation.
2
So, the complexity of the above algorithm is O(n ).
14.4 BEST CASE, WORST CASE AND AVERAGE CASE COMPLEXITY
• Best case complexity: For any input of size ‘n’, the function takes the minimum time or minimum number of steps
for execution is called the best case complexity. It defines the lower bound of an algorithm.
• Worst case complexity: For any input of size ‘n’, the function takes the maximum time or the maximum number of
steps required for execution is called the worst case complexity. It defines the upper bound of an algorithm.
• Average case complexity: In the average case analysis, we take all possible input combinations and calculate its
individual computation time and then calculate the average of all the data. So, this calculates the average time
taken by an algorithm for execution.
The above three cases can be depicted graphically as given below.
Number of Worst Case
steps Complexity
Average Case
Complexity
Best Case
Complexity
1 2 3 4 N
(Input size)
Let us again consider the algorithm of linear search as an example.
If the number to be searched is present in the first position of the array, then the loop executes only once. So, the best
case complexity of linear search is O(1) or constant.
560560 Touchpad Computer Science-XII

