Page 568 - Computer science 868 Class 12
P. 568

3.  Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm.          [ISC 2018]
                  4.  What is the worst case complexity of the following code segment:
                      for(int x = 1; x<=a; x++)                                                                [ISC 2016]
                      {
                      statements;
                      }
                      for(int y = 1; y <= b; y++)
                      {
                      for (int z = 1; z <= c; z++)
                      {
                      statements;
                      }
                      }
                      How would the complexity change if all the three loops changed to N instead of a, b and c?
                  5.  Determine the complexity of the following code snippet:
                     a.  void push(int n)
                      { if(top==size-1)
                            System.out.println("Stack full.........overflow");
                        else
                           a[++top]=n;    }
                     b.  void deletebeg(Node start)
                      {
                      Node ptr=start;
                      start=ptr.next;
                      ptr.next=null;
                      }
                    c.  int i=1;
                      do
                      {
                      System.out.println(i);
                      i=i+1;
                       }while(i<=n);
                     d.  for(int  i = 1; i <x ; i++)
                      {
                          if(x % i == 0)
                         {
                             sumOfFactors = sumOfFactors + i;
                         }
                      }
                          if(x == sumOfFactors)
                             System.out.println(x + " is a perfect number. " );
                          else
                            System.out.println(x + " is not a perfect number. " );
                      }
                                          Previous Years' Questions


                                                        n
                                                2
                     Compare the two complexities O(n ) and O(2 ) and state which is better and why.           [ISC 2019]
                Ans. O(n ) is better than O(2 )
                       2
                                      n
                     Let us see with the help of an example.
                     Suppose n = 8
                         2
                     2
                     n  = 8  = 64
                         8
                     2  = 2  = 256
                     n
                                           n
                                                        2
                                                                                            2
                     Therefore, the complexity in 2  is higher than n . If n increases, 2  increases much more than n . Therefore, the time complexity is
                                                                     n
                                      n
                       2
                    O(n ) is better than O(2 ).
                566566  Touchpad Computer Science-XII
   563   564   565   566   567   568   569   570   571   572   573