2 3. Consider the following algorithm implemented in python: (18 points) def cho

Question

2 3. Consider the following algorithm implemented in python: (18 points) def chocolateAlgorithm (n) #Input is a positive integer n if n= 1: return 1 else: return chocolateAlgorithm (n-1)2 n -1 a-) Set up a recurrence relation for this function's values and solve it to determine what this algorithm computes. b-) Set up a recurrence relation for the number of multiplications made by this algorithm and solve it. c-) Set up a recurrence relation for the number of additions/subtractions made by this algorithm and solve it

Explanation / Answer

Solution:

a)

There recurrence relation of the given snippet is T(n-1) + (2*n -1)

at n= 5

T(5) = T(4) + (2*5-1)

T(4)= T(3) + (2*4-1)

T(3)= T(2) + (2*3-1)

T(2)= T(1) + (2*2-1)

T(1)= 1, base case

Now all the values generated here will be added which are loaded in to stack memory

1+3+5+7+9= 25, and we know that 5^2= 25

This means that the function is computing square of a number.

b)

Recurrence relation for number of multiplication is:

T(n)= n-1

T(5)= 4 multiplications will be done.

c)

T(n)= 2(n-1).

I hope this helps, please let me know in case of any doubt.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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