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
   557   558   559   560   561   562   563   564   565   566   567