Page 565 - Computer science 868 Class 12
P. 565

♦ 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.
                                                                                      N
                                                           2
                                                                 3
                      ♦ The different Big O notations are O(1), O(N), O(N ), O(N ), O(log N), O(N log N), O(2 ), O(N!).
                      ♦ The term which dominates the algorithm the most is called the dominant term and is only included in the Big O notation.
                      ♦ The worst case complexity of an algorithm is the function defined by the maximum number of steps taken on any instance of
                     size n. It represents the curve passing through the highest point of each column.
                      ♦ The best case complexity of an algorithm is the function defined by the minimum number of steps taken on any instance of size
                     n. It represents the curve passing through the lowest point of each column.
                      ♦ The average case complexity of an algorithm is the function defined by the average number of steps taken on any instance of
                     size n.






                                                                MIND DRILL



                     Solved Questions


                 A.  Tick ( ) the correct option:
                    1.  Computational complexity of an algorithm refers to the ………………… .
                       a.  number of operations for one iteration of the algorithm
                       b.  logic to find solution to a problem
                       c.  read write operation performed during one complete iteration of the algorithm
                       d.  All of these
                    2.  Which case does not exist while calculating complexity?
                       a.  Best case                                   b.  Better Case
                       c.  Worst case                                  d.  Average case
                    3.  Big O notation of Bubble Sort is ………………… .
                       a.  O(N)                                        b.  O(Log N)
                                                                            2
                       c.  O(N log N)                                  d.  O(N )
                    4.  Big O notation represents the ………………… .
                       a.  lower bound                                 b.  lower and upper bounds
                       c.  upper bound                                 d.  None of these
                    5.  The complexity of push and pop operations in stack is ………………… .
                       a.  O(N)                                        b.  O(1)
                       c.  O(N log N)                                  d.  O(N )
                                                                            2
                   Answers
                     1.  a     2.  b     3.  d     4.   c   5.   b

                 B.  Fill in the blanks:
                    1.  Complexity of linear search is ………………… .
                    2.  The Big O notation for traversing a linked list is ………………… .
                    3.  The………………… are ignored in a BigO notation.
                    4.  The worst case complexity of Merge sort is ………………… .
                    5.  The………………… case complexity represents the lower bound of an algorithm.

                   Answers
                    1.  O(n)          2.  O(log N)          3.  constants       4.  O(N log N)      5.  best



                                                                                                                       563
                                                                              Computational Complexity and Big O Notation  563
   560   561   562   563   564   565   566   567   568   569   570