recursion runtime.py

def fn_d(n: int) -> int:
  if n <= 1:
    return 1
  count = 0
  for x in range(n):
    count += x
  return fn_d(n//2) + fn_d(n // 2) + count

# runtime: O(n log n)
# The loop for adding up count iterates (n) times doing constant addition operation. This is O(n). 
# This work is done every time the recursive calls are done and the levels of the recursive tree is log n.


def fn_e(n: int) -> int:
  if n == 0:
    return 1
  return fn_e(n // 2) + fn_e(n // 2)

# runtime: O(n)
# Each recursive call branches into two, with half the size of the input. These two can cancel out leading to n time complexity
# The amount of work doubles at each level of recursion while n is halved each call.



def fn_g(n: int, m: int) -> int:
    if n <= 0 or m <= 0:
        return 1
    return fn_g(n//2, m) + fn_g(n, m//2)

# runtime: O(max(n,m))
# This is like fn_e. The number of levels/recursive calls made depends on whichever is larger of n and m. 
# Bigger one will take longer to reach the base case while n and m are halved in each function call.