Solving this recurrence relation Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction
$$
{\rm T}\left(n\right)
={\rm T}\left(\left\lfloor{n \over 2}\right\rfloor\right)
+{\rm T}\left(\left\lfloor{n \over 4}\right\rfloor\right)
+{\rm T}\left(\left\lfloor{n \over 8}\right\rfloor\right)
+n
$$
I'm aware a similar question has been asked here before, but that thread dates back to a year or so ago and I never really understood the rationale behind the answer given (see here: Need some help with this recurrence equation). My guess is that it is in $\Theta(n)$, but I'm not sure how to get a more precise relation than that. I've tried expanding out the recurrence a bit, but I'm not seeing any obvious pattern.

Take k = max{8, T(1)} and you can easily show by induction that T(n) is no greater than kn. The lower bound is trivial.
