Algorithms:

1. This is the backward substitution to get the time complexity of a recursive algorithm. Follow the example:

Now solve the following recurrence relation as described above. You have to present intermediate steps and time complexity as described above.

M(n) = 2*M(n 1) // recurrence relation

M(1) = 2 // initial condition

....

============================================================================================================================================

2. Consider the following recursive algorithm.

Algorithm Q(n)

if n = 1

return 1

else

return Q(n - 1) + 2 * n 1

(a) Set up a recurrence relation for the number of multiplications made by this algorithm.

(b) Provide an initial condition for the recurrence relation you develop at the question (a).

(c) Solve the recurrence relation of the question (a) and present the time complexity as described at the question number 1.

============================================================================================================================================

3. Consider the following recursive algorithm. Set up a recurrence relation and an initial condition for the comparison operation at the if n = 1 in the line number 3.

[Hint: Use C(n) to indicate the number of comparisons for the array A with the size n. Then, the initial condition would be either C(1) or C(0).]

// Recurrence relation M(n) = M(n-1) + 1 M(0) 0 // Initial condition // Replace M(n-1) with "M(n-2) // Replace M(n-2) with "M(n-3) + 1 M(n) = M(n-l ) + 1 1 [Mn-2) + 1] + 1 = M(n-2) 2 = M(n-3) + 3 - M(n-i) +i M(n-n) + n =M(0) + n =0+n