Defining Recursive Complexities
Some algorithms are conceptually recursive, and so it may be useful to express their complexities recursively. This is generally going to be of the form:
where ) is the complexity of a single iteration of the algorithm on element and describes the relative size of the input to the following iteration. For example, a binary search has a constant overhead for each iteration and reduces the search size by a factor of each time, so its complexity is given recursively by
Solving Recursive Complexities
Given the above example, we may intuitively recognise it as equivalent to , but in order to solve similar but more complex or less familiar formulae we require a formal method.
We explore here three such methods: