I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$.
Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from the top, but I can't seen to find the $θ$ bound.
I'd be glad for some help.
Thanks in advance, Yaron.
Take a peek at Leighton's "Notes on Better Master Theorems for Divide-and-Conquer Recurrences" (1996). This is sadly not formally published anywhere I'm aware of. For a recurrence: $$ T(n) = g(n) + \sum_{1 \le k \le n} a_k f(b_k n + h_k(n)) $$ where $a_k > 0$ and $0 < b_k < 1$, $h_k(n) = O(n / (\log n)^2)$, and $\lvert g(n) \rvert = O(n^c)$ for some constant $c$. For the typical case of "round up/down to the next integer" $h_k$ this is satisfied.
Compute $p$ such that: $$ \sum_{1 \le k \le n} a_k b_k^p = 1 $$ then: $$ T(z) = \Theta \left( z^p \left( 1 + \int_1^z \frac{g(u)}{u^{p + 1}} \, \mathrm{d} u \right) \right) $$ in your case, $g(n) = n$, which satisfies the condition. $$ a^p + b^p = 1 $$ gives $p = 1$, your $g(n) = n$ gives: \begin{align} f(z) &= \Theta(n^1(1 + \int_1^n \frac{u}{u^2} \mathrm{d} u)) \\ &= \Theta(n \log n) \end{align}