Page 411 - computer science (868) class 11
P. 411

•  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.

                     13.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.

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


                 13.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.




                                                                                                                       409
                                                                            Implementation of Algorithms to Solve Problems  409
   406   407   408   409   410   411   412   413   414   415   416