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

