# 2.10 Analyzing the time complexity of recursive algorithms

### Recurrence relations

The runtime complexity T(N) of a recursive function will have function T on both sides of the equation. Ex: Binary search performs constant time operations, then a recursive call that operates on half of the input, making the runtime complexity T(N) = O(1) + T(N / 2). Such a function is known as a recurrence relation: A function f(N) that is defined in terms of the same function operating on a value < N.

Using O-notation to express runtime complexity of a recursive function requires solving the recurrence relation. For simpler recursive functions such as binary search, runtime complexity can be determined by expressing the number of function calls as a function of N.

# When the low and high arguments are equal, BinarySearch does not make a recursive call. True False Suppose BinarySearch is used to search for a key within a list with 64 numbers. If the key is not found, how many recursive calls to BinarySearch are made? 1 6 64 Which function is a recurrence relation? T(N) = N² + 6N + 2 T(N) = 6N + T(N⁄4) T(N) = log N

### Recursion trees

The runtime complexity of any recursive function can be split into 2 parts: operations done directly by the function and operations done by recursive calls made by the function. Ex: For binary search's T(N) = O(1) + T(N / 2), O(1) represents operations directly done by the function and T(N / 2) represents operations done by a recursive call. A useful tool for solving recurrences is a recursion tree: A visual diagram of a operations done by a recursive function, that separates operations done directly by the function and operations done by recursive calls.