Answer and Explanation:
For the first iteration of i for loop 1 to n, the j for loop will run from 2 to n times. i.e. n-1 times.
For the second iteration of i for loop, the j for loop will run from 3 to n times. i.e. n-2 times.
From the third to the last iteration of i for loop, the j for loop will run n-1 to n times. i.e. 2 times.
From the second to the last iteration of i for loop, the j for loop will run from n to n times. i.e. 1 time.
For the last iteration of i for loop, the j for loop will run 0 times because i+1 >n.
Hence the equation looks like below:
1 + 2 + 3 + ...... + (n-2) + (n-1) = n(n-1)/2
So the number of total iterations is n(n-1)/2.
There are two operations per loop, i.e. Comparison and Multiplication, so the iteration is 2 * n(n-1)/2 = n ^2 - n
So f(n) = n ^ 2 - n
f(n) <= n ^ 2 for n > 1
Hence, The algorithm is O(n^2) with C = 1 and k = 1.
4) Suppose n = 1, then i = 2
n = 2, then i = 4
n = 3, then i = 6
n = 4, then i = 8
So the value of i is doubled for each iteration of while loop.
So i = 2 ^ n
i is growing at the rate of a power of 2, so the number of operations is log(2n)
Hence the algorithm is O(log(n)).
