HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Run time of recurrence with five uneven calls

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
callsfivewithrecurrencetimeunevenrun

Problem

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?

Solution

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

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

Context

StackExchange Computer Science Q#79781, answer score: 4

Revisions (0)

No revisions yet.