Algorithm Analysis

Question

I have an algorithm with the following pseudocode:

R(n)
if(n = 1)
  return 1
else
  return(R(n-1) + 2 * n + 1)

I need to setup a recurrence relation for the number of multiplications carried out by this algorithm and solve it.

Is the following right?

R(1) = 0
R(n) = R(n-1) + n^2

Every recursive call does one multiplication operation. There are n-1 recursive calls. — G. Bach
– G. Bach, Commented May 2, 2013 at 21:42

unxnut · Accepted Answer · 2013-05-02 21:43:08Z

3

You are performing only one multiplication per step. Therefore, the relation will be:

R(n) = R(n-1) + 1

answered May 2, 2013 at 21:43

unxnut

8,8993 gold badges30 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

James Waldby - jwpat7 · Accepted Answer · 2013-05-02 23:09:24Z

In the algorithm as shown, R(n) is calculated by adding R(n-1) to 2*n+1. If 2*n is calculated using a multiplication, there will be one multiplication per level of recursion, thus n-1 multiplications in the calculation of R(n).

To compute that via a recurrence, let M(n) be the number of multiplications used to compute R(n). The recurrence boundary condition is M(1) = 0 and the recurrence relation is M(i) = M(i-1) + 1 for i>1.

Errors in writing “R(1) = 0; R(n) = R(n-1) + n^2” as the recurrence for the number of multiplications include:
• R() already is in use as a function being computed, hence re-using R() as the number of multiplications is incorrect
• Each level of recursion in the algorithm adds one multiplication, not n² multiplications.

Note, R(n) = 1 + 5 + 7 + ... + 2n+1 = 1 + 3 + 5 + 7 + ... + 2n+1 - 3 = n²-3; that is, function R(n) returns the value n²-3.

Collectives™ on Stack Overflow

Algorithm Analysis

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related