Question

Give a big-O estimate for the number of operations,

Answer 1

Answer:

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.