Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

290 Views Asked by At

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$.

I want to show that $W(n)\in \Theta(n)$.

Attempt 1

I understand the technique used in this question that solves $T(n)=2T(n/2)+n \log n$ by considering $n=2^m$ and letting $f(m)=T(2^m)$.

However, I don't see how to apply this to the $n/5$ and $7n/10$ in $W(n)$'s definition because the fractions don't nicely reduce any base.

Attempt 2

I have considered using the Master theorem with $W(n)\leq {\tilde W}(n) = a W(n/b)+(n)$. With $W$ monotonic increasing, $W(n/5)\leq W(7n/10)$, and thus $W(n) \leq 2 W(7n/10) + \Theta(n)$. Applying Case 1 where $f(n)\in O(n^c)$ from the Wikipedia page gives $c = 1 < log_b a = log_{10/7} 2 = 1.94$ and shows ${\tilde W}(n) \in \Theta(n^{\log_b a}) = \Theta(n^{1.94})$, which doesn't seem useful to show $W(n)\in \Theta(n)$.