patternMinor
Run time of recurrence with five uneven calls
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?
$$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)$.
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.