Page 566 - Computer science 868 Class 12
P. 566

C.  Answer the following questions:
                  1.  What is Complexity?                                                                      [ISC 2014]
                Ans. Complexity refers to the measure of performance of an algorithm with respect to amount of space and time taken.
                  2.  What is Big O notation?                                                             [ISC 2014, 2010]
                Ans. Big O notation is the measurement of growth rate of an algorithm, i.e., the change in algorithm’s performance when its input size
                    grows.
                  3.  What is a dominant term?
                                                                                                                 2
                Ans. The term which has maximum effect on algorithm’s performance is called a dominant term. For a complexity defined as an +bn+c,
                                                             2
                                      2
                    the dominant term is n  and it’s Big O notation is O(n ).
                  4.  What is the role of constant in complexity?                                              [ISC 2012]
                Ans. Constants are ignored, while determining the algorithm’s performance.
                  5.  What is the best case, worst case and average case complexity?                           [ISC 2011]
                Ans. 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.
                  6.  What is the worst case complexity of the following code segment?                         [ISC 2013]
                      for(int p=0; p<N; p++)
                      {
                      for(int q=0;q<M; q++)
                      {
                      Sequence of statements
                      }
                      }
                      for(int r=0;r< X;r++)
                      {
                      Sequence of statements
                      }
                     How would the complexity change if all the loops went up to the same limit N?
                Ans. For each iteration of p loop, q loop will execute M times.
                    For N iterations of p loop, total number of steps executed is M*N. So, the complexity is O(M*N).
                    The r loop executes X times. The complexity is O(X).
                    The worst case complexity of the above code is O(M*N +X).
                                                                          2
                                                                                2
                    If all the loops are changed to N, then the complexity changes to O(N  + N). N  is the dominant term. So, the complexity will be
                       2
                    O(N ).
                  7.  Determine the complexity of the code given below.
                      for ( int i=0 ; i<n ; i=i*2)
                      { System.out.println ( i ); }
                Ans. The value of i is increasing 2 times in each iteration. Say p is the total iterations, then
                     P
                    2  >=n (number of terms)
                    Taking log on both sides
                    P log 2= log n
                    So, the complexity is O(log N).







                564564  Touchpad Computer Science-XII
   561   562   563   564   565   566   567   568   569   570   571