Big O, recursive runtimes

Recursive runtimes can have simple runtimes. For instance.

function factorial(n) {
  if(n === 0) return 1;
  return n * factorial(n-1);
}

Has an O(n) runtime, because we’re just going through a loop (recursion is also in a sense a loop) until we get to our value.

This changes if the return value of our recursive value calls multiple recursions such as

function notFactorial(n) {
  if(n === 0) return 1;
  return notFactorial(n-1) + notFactorial(n-1);
}

These problems give us a depth of O(2^n) because as we look for each new solution for notFactorial, the solution of that problem is split up into two branches of a smaller version of our original notFactorial function