Writing and solving a recurrence that counts the number of multiplications in this code?

Question

Let M(n) be the number of multiplications that the function fct does.

     //precondition: n>0
     int fct (const int A[], int n) {
          if (n==1)
             return A[0]*A[0];
          else return A[n-1] * fct(A,n-1) * A[n-1];
     }

write recurrence relation for M(n) where n is the number of elements in the array

Solve the recurrence relation to obtain M(n) in terms of n

Write the resulting expression of part 2 in big O notation

So this was a quiz, and I have the answer key, but not too sure how this was computed, M(n)=2n-1 with O(n)..I do not know how this was determined, can someone explain? Thanks

Answer 1

Let's look at what each call does. Each call, when n > 1,

• Does exactly two multiplications, then
• Makes a recursive call on a problem of size n - 1

Therefore, we can write the recurrence as

• M(1) = 1
• M(n) = 2 + M(n-1)

If you use the iteration method, you'll notice this pattern:

• M(1) = 1
• M(2) = M(1) + 2 = 3
• M(3) = M(2) + 2 = 5
• M(4) = M(3) + 2 = 7
• ...
• M(n) = 2n - 1

Now that you have this, you can write it asymptotically as M(n) = Θ(n).

Hope this helps!