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.

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.

Suppose a recursive function's runtime is T(N) = 7 + T(N ā 1).

Suppose a recursive function's runtime is T(N) = N + T(N ā 1).