Page 559 - Computer science 868 Class 12
P. 559

14.1 TIME AND SPACE COMPLEXITY
                 From the above discussions we can derive that complexity depends on two factors:

                 1.  Space complexity: It is the amount of memory space required to run an algorithm. An algorithm which requires the
                   least memory is considered more efficient.

                 2.  Time complexity: It is the total time taken to execute the instructions (steps) of a program. An algorithm which is
                   designed using the least number of steps is considered more efficient. However, time complexity is a function of
                   input size.

                 The performance of an algorithm is also dependent on several other external factors like:
                 a.  Speed of the computer
                 b.  Size of RAM memory in the computer
                 c.  Operation system running on the device
                 d.  Compiler used for executing the program


                     14.2 BIG O NOTATION
                 To analyse complexities and representing them using the mathematical notations, the concept of Asymptotic Notation
                 is used. ‘Asymptotic’ describes an expression where the value of the variable tends to infinity. This method thus
                 describes the limiting behaviour of an expression which is useful in representing the running time complexity of the
                 algorithm.

                 The different asymptotic notations are:
                 •  Big O Notation (O(n)): It represents the upper bound or the longest time taken by an algorithm to execute, for a
                   given input size. It is used for calculating the worst case time complexity of an algorithm or the longest time taken
                   in execution of a program.
                 •  Omega Notation (Ω(n)): It represents the lower bound or the least time taken by an algorithm of given input size
                   to complete its execution, i.e., it is used for measuring the best case time complexity of an algorithm.
                 •  Theta Notation (Θ(n)): It has the characteristics of both Big O and Omega notations, as it represents the lower and
                   upper bounds of an algorithm.
                 The Big O notation measures the growth rate of an algorithm. It determines the change in the performance of an
                 algorithm with increase in its input size. Big O notation is also used for comparing the performance of two or more
                 algorithms. Some common Big O notations of an algorithm are shown below.

                         Big O notation                                  Example
                         1. O(1)        •  Pushing or popping an item on the top of a stack
                                        •  Inserting an item in rear end or deleting an item from the front end of a queue
                                        •  Adding or removing nodes in the front of a linked list
                                        The complexity remains constant as the algorithm is not affected by increase in input size.
                         2. O(N)        •  Linear search in an unsorted array
                                        The change in complexity is also linear and is directly proportional to the number of inputs.
                                        If the input size increases or decreases by ‘x’, the growth also changes by ‘x’.
                         3. O(N )       •  Bubble Sort
                              2
                                        •  Selection Sort
                                        •  Insertion Sort
                                        The change is quadratic in nature and is directly proportional to the square of the input
                                        size. If the size is n=10, then the number of steps taken is 100. It becomes 400 when the
                                        size changes to 20 and so on.



                                                                                                                       557
                                                                              Computational Complexity and Big O Notation  557
   554   555   556   557   558   559   560   561   562   563   564