Consider the algorithm Algorithm Mysteryn for i leftarrow 1

Consider the algorithm Algorithm Mystery(n) for i leftarrow 1 to n-1 for leftarrow i+1 to n for k leftarrow 1 to j ...c basic operations Find the number of basic operations for the algorithm above. Express in summation and solve. What is the efficiency class of this algorithm near, quadratic, etc.)?

Solution

a)

First try to go through each loop one by one. Start from outermost loop.

So when i = 1 , we will interate j from 2 to n, here n can be any big number.

and k will interate from (1 to 2), (1 to 3), ... (1 to n) as it is from 1 to j so basically it will do

2c basic operation for j = 2, and 3c basic operation for j = 3 and so nc basic operation for j = n.

Similarly for i = 2,

j will iterate from 3 to n

so k will iterate (1 to 3), (1 to 4) ... (1 to n), so basically

3c operations for j = 3, 4c operation for j = 4, nc operation for j = n.

You might have noticed that when we are incrementing i, starting number of basic operation is getting incremented

so basically we started with 2c operation in i = 1, and 3c basic operations in i = 2 up until nc basic operation. Similarly we will start with 4c basic operation for i = 3, and only nc basic operation for i = n - 1 as j will have only one iteration i.e. j = n and k will iterate from 1 to n

so basically

2c is appearing first time, 3c is appearing first two times, 4c is appearing first 3 times and nc is appearing first n - 1 times. Basically i + 1 is appearing i times

so we can say a(n) = n*(n - 1), here n is the number of basic operations(n >= 2) and a(n) is number of times there are appearing. So 2c is only one times, 3c => 2 times, 4c => 3 times and so on.

Now this is the sequence we are getting

2c, 6c, 12c, 20c, 30c, 42c, .... n*(n - 1)c

You can clearly see that above sequence is summation of sum of n numbers and sum of square of numbers

so it is equivalent to 1 + 2^{2 +} 3² + ... n² and 1 + 2 + 3 + 4 + 5 ... n

=> 2 + 6 + 12 + 20 + 30 + .....

=> n*(n + 1)*(2*n + 1) / 6 + n*(n + 1) / 2

b)

You can clearly see it is cubic from above term. n*(n + 1)*(2*n + 1) ~ n³