Finding Big O from non-standard recurrence relations without master method

A friend taking their data structures and algorithms (DSA) class asked me a question about recurrence relations. Consider this:

$ \text{Find } O(T(n)), \text{where} ~ T(n) = 3T(\frac{2}{3}n) $

This was derived from pseudocode where 3 recursive calls are made per function call, each splitting the subproblem into (2/3) N.

Nevermind the practicality, its a DSA course after all.

It doesn’t fit any of the common recurrence relations. Tools like the master method are not taught at entry level DSA classes (or even bootcamps)! Yet tricky non-standard recurrence relations are tested 💦

So, there is a general-ish way to solve recurrence relations without using master method.

T(n) + a(T/b) + O(k) Formula

$ \text{Let } T(n) = aT(\frac{n}{b}) + O(k), \\ ~ \\ O(T(n)) = \begin{cases} O(k * n^{\log_{b}a}), ~~~ k \ne 1 \\ O(\log_b(n)), ~~~ k = 1 \end{cases} \\ ~ \\ \text{Where } b \ne 1. $

You can stop reading now, unless you want to know why.

Ok. Why?

Recursion Trees 🌲

A good way to approach these kinds of questions is to draw a recursion tree out to visualize the problem.

From the tree, we can see that the total cost = (how many nodes) * (cost of each node). We can use the cost equation to derive our big O.

For this, we need to know 2 things.

1. How many levels are there in the tree?

Max number of levels for $T(\frac{n}{b})$ in the tree = $\log_{b}(n) \text{ levels}$

Proof shown below.

2. What is the cost per node?

Cost per node is k = O(k) as defined by the recurrence relation.

Finding the Cost

We can now find the total cost, and by extension the big O of the recurrence relation.
The sum of the cost fits nicely into the sum of geometric progression (GP) formula.

Recall that GP = $ar^0 + ar^1 + ar^2 + … + ar^n$, where

$S_n = a(\frac{r^n-1}{r-1})$, where a is a constant.

Going back to my friend’s problem,

$ \text{Consider } 3T(2n/3) + k, O(k) = O(1) $

From the recursion tree, we can see that

$ \sum\limits_{\text{Cost}} = k(3^0 + 3^1 + 3^2 + … + 3^{\log_{\frac{3}{2}}n}) \\ \sum\limits_{\text{Cost}} = (k)\frac{(3^{\log_{\frac{3}{2}}n} - 1)}{3-1} \\ \sum\limits_{\text{Cost}} = \frac{k}{2} (3^{\log_{\frac{3}{2}}n} - 1) \\ ~ \\ O(T(n)) = O(\frac{k}{2} (3^{\log_{\frac{3}{2}}n} - 1)) \\ ~ \\ O(T(n)) = O(3^{\log_{\frac{3}{2}}n}) \text{ , ignore k as O(k) = O(1)}\\ ~ \\ \because a^{\log_{b}(c)} = c^{\log_{b}(a)}, \\ ~ \\ O(T(n)) = O(n^{\log_{\frac{3}{2}}3}) ~ \square $

Nice. Let’s generalise this, and account for cases where $O(k) \ne O(1)$.

General Form 💫

Generalising $T(n) = aT(n/b) + O(k)$,

$ \sum\limits_{\text{Cost}} = k(a^0 + a^1 + a^2 + … + a^{\log_{b}n}) \\ \sum\limits_{\text{Cost}} = k\frac{(a^{\log_{b}n} - 1)}{a-1} \\ \therefore O(T(n)) = O(k\frac{(a^{\log_{b}n} - 1)}{a-1}) = O(k* n^{\log_{b}a}) ~ \square $

Oh, but there is a sneaky edge case. What happens when $a=1$?
The sum of the costs will be undefined and the universe will implode.

For that, we can use L’Hopital’s rule.

$ \lim\limits_{a \rarr 1} k\frac{(a^{\log_{b}n} - 1)}{a-1} = \lim\limits_{a \rarr 1} k \frac{\frac{\partial}{\partial a}(a^{\log_{b}n} - 1)}{\frac{\partial}{\partial a}(a-1)} = … = log_b(n) $

The proof¹ for this tricky differentiation is in the footnotes.

But what if $b=1$? The setup will not be applicable. We’ll have to use another solving method 🙈
The sum of costs might no longer be geometric.

In such cases, like $T(n) = T(n-1)$, it forms an arithmetic progression (so solve that instead!).

Sanity Checks 😷

Let’s just check that this formula works for well known recurrence relations.

Tree Traversal

Tree Traversal runs in $O(n)$, and has a recurrence relation of $T(n) = 2T(n/2) + O(1)$

$ O(k) = O(1), b = 2, a = 2 \\ O(T(n)) = O(1) * O(n^{log_2(2)}) = O(n) $ ✅

Binary Search

Binary search runs in $O(\log_{2}(n))$, and has a recurrence relation of $T(n) = T(n/2) + O(1)$.

$ O(k) = 1, b = 2, a = 1 \\ O(T(n)) = O(\log_{2}(n)) $ ✅

Merge Sort

Merge sort runs on $O(n\log_{2}n)$ and has a recurrence relation of $T(n) = 2T(n/2) + O(n)$

$ O(k) = O(n), b = 2, a = 2 \\ O(T(n)) = O(n\log_{2}(n)) $ ✅

It works! At least for these cases + my own testing. You can plug and play this in your exams or whatever – it SHOULD work but I’m not a math major so yea 🙃

Proof - Max level of recursive tree

Proof, done hand-wavily (once again, I’m not a math major or computer scientist 💀 ):

Intuition: The max levels of the tree with starting size N is how much N can be divided by the subproblem size.

Formally,

$b = 2$

• Consider $T(n/2)$
• Assume that the tree stops growing at base case $n/2 = 1$
• By observation, maximum number of levels = number of times n can be divided by 2.
• This follows the definition of logarithms²
• So the number of levels is $\log_{2}(n)$

$b = 3$

• Consider $T(n/3)$
• Similarly, max levels = number of times n can be divided by 3
• Following the definition of logarithms, max levels = $\log_{3}(n)$

Let’s generalise b to a integer variable k.

$b = k$

• Consider $T(n/k)$
• Max levels = $\log_{k}(n)$ with the same reasoning

$b = k+1$

• Consider $T(n/(k+1))$
• Max levels = $\log_{k+1}(n)$

By induction, we have $\log_{b}(n) \text{ levels}$

---

1. Consider the numerator.
   $ \text{Let } y = a^{\log_{b}n}, \\ \ln y = \ln a * \log_{b}n \\ ~ \\ \frac{1}{y} \frac{\partial{y}}{\partial{a}} = \frac{1}{a} \log_{b}n \\ ~\\ \frac{\partial{y}}{\partial{a}} = \frac{y}{a} \log_{b}n \\ ~ \\ \frac{\partial{y}}{\partial{a}} = a^{\log_b n -1} \log_{b}n ~~ \text{(sub in y)} $
   
   So,
   $ \lim\limits_{a \rarr1} ~ k \frac{\frac{\partial}{\partial a}(a^{\log_{b}n} - 1)}{\frac{\partial}{\partial a}(a-1)} = \lim\limits_{a \rarr1} ~ k\frac{a^{\log_b n -1} \log_{b}n}{1} \\ ~ \\ \text{When a = 1, it evaluates to } \log_{b}(n) ~ \square $ ↩︎

2. The logarithm is the inverse function to exponentiation. Exponentiation, $a = b^n$ can be interpreted as multiplying b by n times. Since log is its inverse, we can think of $\log_{b}a = n$ as the number of times a can be divided by b (n times!). ↩︎