Page 560 - Computer science 868 Class 12
P. 560

4. O(log N)    •  Binary Search in a sorted array
                                     The change is logarithmic in nature. We can calculate that with increase in input size the
                                     growth rate of linear search is much higher than binary search.
                      5. O(N )       •  Matrix multiplication
                           3
                                     •  Simultaneous linear equations
                                     The growth rate is cubic in nature. For n=10, number of steps required is 1000. When n=20
                                     it jumps to 8000 and so on.
                      6. O(N log N)  •  Merge Sort
                                     •  Quick Sort
                                     The complexity is better than some other sorting algorithms where complexity changes in
                                     quadratic manner.
                      7. O(2 )       •  Tower of Hanoi
                           N
                                     The algorithm doubles with every additional input. When n is 2, 4 steps are executed, which
                                     becomes 8 when n is 3 and 16 when n is 4.
                      8. O(N!)       •  Travelling salesman problem using a brute-force approach
                                     The algorithm has a run time proportional to the factorial of the input size. When n=2, the
                                     algorithm runs 2 times, 6 times for n=3, 24 times for n=4 and so on.

              Let us compare the Big O notations of different algorithms with change in input size.

                                  WComplexity         Size=10           Size=20           Size=100
                                      O(1)               1                 1                 1
                                     O(N)               10                20                100
                                     O(N )              100               400              10000
                                        2
                                        3
                                     O(N )             1000              8000             1000000
                                     O(2 )             1024             1048576          1.26 × 10 30
                                        N
              Comparing the three Big O notations, we can easily conclude that the most efficient among the five is O(1) and the
              least efficient is O(2 ).
                                N

                  14.3 COMPLEXITY CALCULATIONS AND DOMINANT TERM
              Complexity calculations are done by analysing each step of a program. Let us discuss them one by one.
              1.  Single loop: Let us take a simple loop as an example.

                  for(int i=1 ; i<=n ; i++)
                     System.out.println(i);
                Let us assume that the time taken to execute the print statement = t
                Number of times the loop executes = n
                Total time taken = t * n
                So, the complexity is O(n).
              2.  Nested loops: Let us consider the following nested loop.

                  for(int i=1;i<=n;i++)
                  {
                     for(int j=1;j<=n;j++)
                    {  System.out.println(j);}
                  }




                558558  Touchpad Computer Science-XII
   555   556   557   558   559   560   561   562   563   564   565