Page 438 - Cs_withBlue_J_C11_Flipbook
P. 438

•  Space factor: It is measured by calculating the maximum memory space required by an algorithm. The algorithm
                 that utilises the least memory is considered the best one.
              •  Time factor: It is the total time taken by an algorithm to execute each step with respect to its input size. The
                 algorithm that performs the task in the least number of steps is considered the most efficient one.

              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 to analyse  of an algorithm. 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.

                   14.4 PROPERTIES OF WRITING A GOOD ALGORITHM
              An effective and efficient algorithm must have the following properties:
              •  Accuracy: An algorithm must provide the correct solution to a given problem in an unambiguous manner.
              •  Finiteness: An algorithm must produce the correct output after a finite number of steps and terminate after that.
              •  Input: An algorithm must receive 0 or more inputs in a specified format.
              •  Output: An algorithm must produce one or more outputs in a specified format.
              •  Language independence: An algorithm must be language-independent, which means that the instructions when
                 coded in any programming language will produce the same result.
              •  Effectiveness: Each instruction in an algorithm should be adequate and provide the correct solution to the problem.
              •  Memory: Multiple algorithms may provide the correct solution to a given problem, but the one which utilises less
                 memory is better.
              •  Time: Lesser the time taken to produce the correct output to a problem, the better is the algorithm.

                   14.5 SOME STANDARD ALGORITHMS
              Algorithms for some of the important concepts of programming are given below:


              14.5.1 Algorithms of Decision Making Statements
              Problem 1: Write an algorithm to find the greatest of three numbers.

              Step 1:  Start.
              Step 2:  Accept three numbers in variables a, b, and c.

              Step 3:  If a > b then go to Step 4, else go to Step 5.
              Step 4:  If a > c then assign g = a, else assign g = c, go to Step 6.




                436436  Touchpad Computer Science-XI
   433   434   435   436   437   438   439   440   441   442   443