Your question is Analyzing Code Complexity. Take a moment with it on the right.
Talk me through your thinking if you like. When you're confident, submit your answer and I'll grade it like a real screen (7/10 or better passes).
SIXT prices multi-day rentals with a recurrence: each additional day's cumulative rate is derived from the two previous days' cumulative rates, with a small per-day discount applied. A backend engineer wrote the recursive function below to compute the cumulative price for a rental of n days. It returns the right number for short rentals in a demo, but nobody has stated its Big O, and it has not been trusted with a real pricing run yet.
def rental_cost(n, base_rate=45.0, _trace=[]):
_trace.append(n)
if n == 1:
return base_rate
discount = 0.98
left = rental_cost(n - 1, base_rate, _trace)
right = rental_cost(n - 2, base_rate, _trace)
return (left + right) * discount
State the Big O time complexity of rental_cost and explain why, in terms of the recursive calls it makes. Then point out anything else about this function you would flag before it's used to price real rentals, and explain the runtime consequence of each.