4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What bound? Upper, lower, tight? Could you specify what kind of bound you want to estimate in your OP? $\endgroup$ – fade2black Aug 6 '17 at 13:13
  • $\begingroup$ @fade2black The upper bound, I'll edit it. $\endgroup$ – z00x Aug 6 '17 at 13:15
  • 4
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – David Richerby Aug 6 '17 at 14:03
  • $\begingroup$ "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? $\endgroup$ – Raphael Aug 6 '17 at 20:21
  • $\begingroup$ Use the Akra–Bazzi theorem. $\endgroup$ – Yuval Filmus Aug 6 '17 at 20:51
4
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ The rule of thumb is essentially the core observation behind the master theorem, isn't it? $\endgroup$ – Raphael Aug 6 '17 at 20:23
  • $\begingroup$ @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. $\endgroup$ – ryan Aug 6 '17 at 20:53
  • $\begingroup$ 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! $\endgroup$ – Raphael Aug 7 '17 at 5:39
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.