Page 567 - Computer science 868 Class 12
P. 567

8.  Determine the complexity of the code given below.
                         for ( int i=0 ; i<n ; i++)
                         {
                         for ( int j=0 ; j<n ; j=j*2 )
                         {
                         System.out.println ( i*10+j );
                         }
                         }
                   Ans. In the j loop, the value of j is increasing 2 times in each iteration. Say p is the total iterations, then
                       P
                       2  >=n (number of terms)
                       Taking log both sides
                       P log 2= log n
                       So, the complexity of j loop is O(log N).
                       Outer i loop is executing n times. So, the complexity of the code is O(N log N).


                      Unsolved Questions


                 A.  Tick ( ) the correct option:
                    1.  The ………………… term is only included in Big O notation.
                       a.  constant                                    b.  quadratic
                       c.  dominant                                    d.  logarithmic
                    2.  The ………………… complexity of an algorithm is the function defined by the maximum number of steps taken on any instance of
                       size n.
                       a.  best case                                   b.  better Case
                       c.  worst case                                  d.  average case
                    3.  Big O notation of Insertion Sort is ………………… .
                       a.  O(N)                                        b.  O(Log N)
                       c.  O(N log N)                                  d.  O(N )
                                                                            2
                    4.  ………………… notation represents the worst case of an algorithm.
                       a.  Big O                                       b.  Omega
                       c.  Theta                                       d.  None of these
                    5.  The complexity of inserting a node at the beginning of a linked list is ………………… .
                       a.  O(N)                                        b.  O(1)
                                                                            2
                       c.  O(N log N)                                  d.  O(N )
                 B.  Fill in the blanks:
                    1.  Complexity of binary search is ………………… .
                    2.  The Big O notation for inserting a node in the linked list is ………………… .
                    3.  ………………… are ignored in a Big O notation.
                    4.  The worst case complexity of Quick sort is ………………… .
                    5.  ………………… case complexity represents the lower bound of an algorithm.

                 C.  Answer the following questions:
                    1.  Differentiate between
                        a.  Space and time complexity
                        b.  Best case and worst case complexity
                                     2
                        c.  Complexity O(N ) and O(log N)
                    2.  Give the meaning of the following common expressions in Big O notation:
                        a. O(N)     b. O(N log N)    c. O(n!)    d. O(1)    e. O(2 )
                                                             N


                                                                                                                       565
                                                                              Computational Complexity and Big O Notation  565
   562   563   564   565   566   567   568   569   570   571   572