3. Give a big- O estimate for the number of operations, where an operation is a

Question

3. Give a big-O estimate for 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).

m := 0

for i := 1 to n

for j := i + 1 to n

m := max(aiaj,m)

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

where an operation is an addition or a multiplication, used

in this segment of an algorithm (ignoring comparisons

used to test the conditions in the while loop).

i := 1

t := 0

while i n

t := t + i

i := 2i

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.