CODEWITHSUNDEEP
algorithm
Martin Spasov
Martin Spasov

Reputation: 313

Is this algorithm analysis correct

I am reading the Algorithm Design Manual and this solution is not in the manual. I spent a solid 30 minutes figuring it out so I was wondering if it is correct. Here is the pseudocode for the function :

function conundrum(n)
  r:=0
  for i:=1 to n do
    for j:=i+1 to n do
      for k:=i+j−1 to n do
        r:=r+1

we solve the first summation and we get

the final equations should be :

Given that the n^4 is negative we can conclude that the running time of this algorithm is

Is it correct ?

Upvotes: 3

Views: 766

Answers (1)

Henry
Henry

Reputation: 43728

The end result is correct, there is at least one error in the detailed calculation: a sum from a to b over 1 is b-a+1.

Also, the sign of the next term is irrelevant (I assume you meant n^2). The runtime would be Theta(n^3) even when the n^2 term is positive.

Upvotes: 3

Related Questions