recurrence relation

to analyze the time complexity of recursive functions we use a mathematical concept called recurrence relation a recurrence defines in terms of for smaller values

, here is defined in terms of

closed form

to solve a recurrence, we find a closed form for it, a closed form for is an equation that defines using an expression that does not involve there is no single method that works for all, we check for patterns and use substitution to get a better understanding, we look at examples

consider the following function that returns the factorial of a given number

def fac(n):
  if n == 1: return 1
  else: return n * fac(n-1)
print([fac(i) for i in range(1,10)])

for fac(n), how many times is fac called? represents the total time of all the operations that take constant time that the function does on every iteration now this is obviously not what we wanna arrive at, we need to arrive at an expression that doesnt have in it we can substitute in because is a function that takes any positive integer

now you probably already see the pattern here, on every iteration the function takes constant time to run, until it reaches the last iteration at which point it we would've times , e.g.:

now we know that the total number of times the function calls itself depends on the initial value of , in this case that number would be , as in, this function calls itself times we substitute to get the total time this function takes to run

so we conclude that

consider the following function that returns the maximum value in a given array

def mymax(arr, l, r):
  if l == r:
    return arr[l]
  return max(arr[l], mymax(arr, l+1, r))
arr = [3, 10, 81, 30, 58, 0, -10]
print(mymax(arr, 0, len(arr)-1))

we need to find a recurrence for this function so we can analyze its time complexity first thing we notice is on every iteration we have a constant time (excluding the recursive call), we call it we can also notice that the variable " " never changes, so our recurrence should only depends on now we can guess that the recurrence equation is: you might be confused (hopefully not) that we wrote even though in the recursive call its , this is because we dont care about the value of the variable itself but rather about how many times the variable causes the function to call itself now if we had written this would suggest that given the value the function runs times which is not correct and so this equals to (using the same proof as the previous problem)

consider the following function that returns the fibonacci number at the given index

def fib(n):
  if n in [1, 2]: return 1
  else: return fib(n-1) + fib(n-2)
print([fib(i) for i in range(1,10)])

for fib(n), how many times is fib called?