Run time of recurrence with five uneven calls

I am trying to figure how to find an upper bound for the running time of a given recurrence relation (without proving the bound) using the Iteration method. The recurrence is:

$$T(n)=2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n$$

I tried to iterate over it and got:

\begin{align} T(n)& =2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n\\[0.5em] & =2\left(2T\left(\frac{n}{25}\right)+3T\left(\frac{n}{50}\right)+\frac{n}{5}\right)+3\left(2T\left(\frac{n}{50}\right)+3T\left(\frac{n}{100}\right) + \frac{n}{10}\right)+n\\[0.5em] & =10T\left(\frac{n}{25}\right) + 6T\left(\frac{n}{50}\right) +9T\left(\frac{n}{100}\right)+\frac{7n}{10} \end{align}

And couldn't know how to continue from here, any hints?

• What bound? Upper, lower, tight? Could you specify what kind of bound you want to estimate in your OP? Aug 6 '17 at 13:13
• @fade2black The upper bound, I'll edit it. Aug 6 '17 at 13:15
• Possible duplicate of Solving or approximating recurrence relations for sequences of numbers Aug 6 '17 at 14:03
• "the running time of a given recurrence relation" -- what do you mean? The running time of computing the recurrence, or the solution of the recurrence? Also, there is no recurrence here; what are the base cases?
– Raphael
Aug 6 '17 at 20:21
• Use the Akra–Bazzi theorem. Aug 6 '17 at 20:51

I'll offer up a more general claim and a proof, you can apply it to your scenario as needed.

The Uneven Split Theorem

Let $c$ and $k$ be positive constants.

Then let $\{a_1, a_2, \dots a_k\}$ be positive constants such that $\sum_1^k a_i < 1$.

We also must have a recurrence of the form:

\begin{align} T(n) & \leq c & 0 < n < max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\}\\ T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\} \end{align}

Claim

Then I claim $T(n) \leq bn$ where:

$$b = \frac{c}{1 - \left(\sum_1^k a_i\right)}$$

Proof by Induction

Basis: $n < max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\} \implies T(n) \leq c < b < bn$

Induction: Assume true for any $n' < n$, we then have

\begin{align} T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\ & \leq cn + b \lfloor a_1 n \rfloor + b \lfloor a_2 n \rfloor + \dots + b \lfloor a_k n \rfloor\\ & \leq cn + b a_1 n + b a_2 n + \dots + b a_k n\\ & = cn + bn \sum_1^k a_i\\[0.5em] & = \frac{cn - cn \sum_1^k a_i }{1 - \left(\sum_1^k a_i\right)} + \frac{cn \sum_1^k a_i}{1 - \left(\sum_1^k a_i\right)}\\[0.5em] & = \frac{cn}{1 - \left(\sum_1^k a_i\right)}\\ & = bn & \square \end{align}

Then we have $T(n) < bn \implies T(n) = O(n)$.

We also know $T(n) = \Omega(n)$ by the recurrence definition, therefore $T(n) = \Theta(n)$.

Next apply it to your recurrence of the form:

$$T(n)=cn + T\left(\frac{n}{5}\right) + T\left(\frac{n}{5}\right) +T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right)$$

I'll leave this for you to figure out the $a_k$'s and $b$.

A pretty quick rule of thumb if the work done per recursion is linear $(cn)$:

• If the constants in the recursion calls sum to less than $1$, it's $O(n)$.

• If the constants sum to exactly $1$, it's $O(n \log n)$.

• The rule of thumb is essentially the core observation behind the master theorem, isn't it?
– Raphael
Aug 6 '17 at 20:23
• @Raphael, basically, except the Master Theorem doesn't apply to these "uneven splits". This is basically a generalization of the Master theorem to uneven recurrences with linear work, which are pretty common. One that comes to mind is the $k$th order statistic algorithm. $T(n) = T(\frac{n}{5}) + T(\frac{3n}{4}) + n$. Not solvable by master theorem, easy to solve with this rule of thumb.
– ryan
Aug 6 '17 at 20:53
• Yes. The common core is the recurrence tree method. Note also the more general Akra-Bazzi theorem. Anyway, you may want to add your theorem to our reference question!
– Raphael
Aug 7 '17 at 5:39

For what it's worth, here is a very simple inductive proof that does not reference more general theorems (since you may or may not be willing to use such a theorem).

I show that $2T(\frac{n}{5}) \geq 3T(\frac{n}{10})$ for all $n \geq 5$.

With that, it becomes clear that $T(n) \leq n + 4T(n/5) \in \Theta(n)$.

Base Case: For $n = 5$,

$$2T(5/5) = 2T(1) = 2(1 + 2T(0) + 3T(0)) = 2(1 + 2 + 3) = 12$$ $$3T(5/10) = 3T(0) = 3$$

Inductive Case: Pick arbitrary $n > 5$. Assume the claim is correct for all relevant $m < n$.

We have,

$$2T(\frac{n}{5}) = 2[\frac{n}{5} + 2T(\frac{n/5}{5}) + 3T(\frac{n/5}{10})] = \frac{2n}{5} + 4T(\frac{n/5}{5}) + 6T(\frac{n/10}{5})$$

And,

$$3T(\frac{n}{10}) = 3[\frac{n}{10} + 2T(\frac{n/10}{5}) + 3T(\frac{n/10}{10})] = \frac{3n}{10} + 6T(\frac{n/5}{10}) + 9T(\frac{n/10}{10})$$

We immediately see that,

$$\frac{2n}{5} \geq \frac{3n}{10}$$

And that, letting $m = \frac{n}{5}$ and $m' = \frac{n}{10}$, using the Inductive Hypothesis, we have

$$4T(\frac{m}{5}) \geq 6T(\frac{m}{10}) \iff 2T(\frac{m}{5}) \geq 3T(\frac{m}{10})$$

$$6T(\frac{m'}{5}) \geq 9T(\frac{m'}{10}) \iff 2T(\frac{m'}{5}) \geq 3T(\frac{m'}{10})$$

Thus, $2T(\frac{n}{5}) \geq 3T(\frac{n}{10})$ as required.

Major as well as minor corrections and comments are very welcome.

We could roughly tight-bound as

$$2T(\frac{n}{10})+3T(\frac{n}{10})+n \leq 2T(\frac{n}{5})+3T(\frac{n}{10})+n \leq 2T(\frac{n}{5})+3T(\frac{n}{5})+n$$

$$5T(\frac{n}{10})+n \leq 2T(\frac{n}{5})+3T(\frac{n}{10})+n \leq 5T(\frac{n}{5})+n$$

Then solve separately $T(n) = 5T(\frac{n}{10})+n$ for the lower bound and $T(n) = 5T(\frac{n}{5})+n$ for the upper bound. In both cases we could take $T(0)= 1$.