Draw the recurrence tree for RecursionMystery and calculate

Draw the recurrence tree for RecursionMystery and calculate its worst-case time complexity.

Input: left: array of n integers Input right: array of n integers Input: n: size of left and right Algorithm Recursion Mystery if n = 1 then if left[1] = right [1] then return left[1] else return 0 end end mind = [n/2] sum = RecursionMystery (left [1... mid], right [1... mid]) sum = sum + RecursionMystery (left [mid + 1...n], right [mid 1..n] for i = 1 to mid do for j = 1 to n- mid do if left [i] = right [mid +j] then Sum = sum + left [i] end if right [i] = left [mid + j] then sum = sum + right [i] end end end return sum

Solution

n! = 1•2•3...n and 0! = 1 (called initial case)

So the recursive defintiion n! = n•(n-1)!

Algorithm F(n)

if n = 0 then return 1 // base case

else F(n-1)•n // recursive call

Basic operation? multiplication during the recursive call

Formula for multiplication

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

is a recursive formula too. This is typical.

We need the initial case which corresponds to the base case

M(0) = 0

There are no multiplications

Solve by the method of backward substitutions

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

= [M(n-2) + 1] + 1 = M(n-2) + 2  substituted M(n-2) for M(n-1)

= [M(n-3) + 1] + 2 = M(n-3) + 3  substituted M(n-3) for M(n-2)

... a pattern evolves

= M(0) + n

= n

Therefore M(n) (n)