Question

Give a big-O estimate the number of operations, where an operation is a comparison or a multiplication, used in this segment of an algorithm (ignoring comparisons used to test the conditions in the for loops, where a1, a2, . . . , an are positive real numbers)

Answer 1

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)).