27.4k views
1 vote
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)

User Debjani
by
8.0k points

1 Answer

2 votes

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

User Olmo
by
7.7k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.