Page 558 - Computer science 868 Class 12
P. 558

14                             COMPUTATIONAL


                                                                      COMPLEXITY AND BIG O

                                                                                   NOTATION














                      Learning Objectives


                  14.1  Time and Space Complexity                   14.2  Big O Notation
                  14.3  Complexity Calculations and Dominant Term   14.4  Best Case, Worst Case and Average Case Complexity
                  14.5  Analysis of Complexity of Common Algorithms



              We live in the modern world today which is controlled by computers and software. Computation is a process of solving
              any problem by mathematical or logical methods using software or applications. With so many different apps available
              in the market for any kind of computation, it becomes essential to analyse them and choose the best one which suits
              our requirement. However, we must also consider that the performance of software is dependent on different system
              resources. The most fundamental system resources are processor and memory. For any given system, the software
              which utilises less memory and takes less time to execute will be the best chosen one.
              Any software is governed by its algorithm. You have learnt about algorithm in previous classes and how to develop it.
              The performance of an algorithm is measured by two factors:
              1.  Effectiveness: The effectiveness of an algorithm is depicted by how accurately it produces a result. In other words,
                 an algorithm should be correct and must produce the desired output for any given set of input.
              2.  Efficiency:  An  efficient  algorithm  is  one  which  produces  accurate  result  in  minimum  time  using  minimum
                 resources.
              Computation involves the process of solving a problem and an algorithm associated with it. Complexity involves the
              study of factors like time taken by an algorithm and space utilised to determine the minimum resource requirement.
              Complexity is thus the measurement of the performance of an algorithm.

              The time taken by an algorithm is the total time taken for executing each step. But number of steps taken is directly
              proportional to its input size.
              Let us take the simplest example: We want to print ‘n’ natural numbers.

              When n=5 then print statement will be executed 5 times. If each execution takes ‘s’ nanoseconds then total time taken
              is 5xs nanoseconds. When n is 100, the time taken is 100xs nanoseconds. We can thus conclude that for any given
              algorithm, its performance depends on its input size.







                556556  Touchpad Computer Science-XII
   553   554   555   556   557   558   559   560   561   562   563