Given the following pseudocode, derive the recurrence relation that represents its time complexity. def fibonacci(n):
if (n==0 or n==1):
return n
return fibonacci(n - 1) + fibonacci(n - 2) Let b and c represent constant values. What is the base case and recurrence step?

Question

Given the following pseudocode, derive the recurrence relation that represents its time complexity.  def fibonacci(n):
    if (n==0 or n==1):
        return n 
    return fibonacci(n - 1) + fibonacci(n - 2) Let b and c represent constant values. What is the base case and recurrence step?

Accepted Answer

T(n) = T(n-1) + T(n-2) + c
T(1) = T(0) = b

Answer

T(n) = T(n-1) + c
T(1) = T(0) = b

Answer

T(n) = T(n-1) + T(n-2) + c
T(1) = n

Answer

T(n) = T(n-2) + c
T(1) = T(0) = b

Crowdly

Given the following pseudocode, derive the recurrence relation that represents i...

Want instant access to all verified answers on learning.monash.edu?