Page 107 - Computer science 868 Class 12
P. 107

While judging the performance of an algorithm, it is important to calculate the total time taken for its execution and
                 it has been observed that the time changes with the change in the input size. Thus, it is necessary to analyse how
                 the time increases or decreases with an increase or decrease in input size. This comparison of the performance of an
                 algorithm can be done using Big O notation.


                                                               Definition
                       Big O notation is a measurement of growth rate of an algorithm with increase in its input size. It defines the upper
                       bound of an algorithm or the maximum time taken by an algorithm for a given input size.




                 While calculating Big O notation, the following three cases may arise:
                 •  Best case complexity: For any input of size ‘n’, the function takes the minimum time or the minimum number of
                   steps for execution. 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 for execution. It defines the upper bound of an algorithm.
                 •  Average case complexity: In the average case analysis, we take all the possible inputs combination and calculate
                   their  individual  computation  time  and  then  calculate  the  average  of  all  the  data.  So,  average  case  complexity
                   calculates the average time taken by an algorithm for execution.

                     3.5 SOME STANDARD ALGORITHMS

                 3.5.1 Algorithm Involving Decision Making Statements
                 Problem 1: Write an algorithm to enter marks of a student and print grade as follows:

                           Marks              Grade
                           upto 90            A
                           89 to 75           B
                           74 to 60           C
                           Below 60           D

                 Step 1:  Start.
                 Step 2:  Accept marks in m.
                 Step 3:  If m>=90 then print ‘Grade A’, go to Step 7.

                 Step 4:  If m>=75 then print ‘Grade B’, go to Step 7.
                 Step 5:  If m>=60 then print ‘Grade C’, go to Step 7.

                 Step 6:  Print ‘Grade D’.
                 Step 7:  Stop.

                                                                                                             2
                 Problem 2: Write an algorithm to find the roots of a quadratic equation. For any quadratic equation ax +bx+c=0 the
                 roots are calculated as:

                                   4
                        -b ± b  2  - a c
                               a 2
                 Step 1:  Start.

                 Step 2:  Accept coefficients a, b and c.


                                                                                                                       105
                                                                            Implementation of Algorithms to Solve Problems  105
   102   103   104   105   106   107   108   109   110   111   112