When drawing a recursion tree, how does b effect the tree if it is given?

Question

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ).

I get how to do it for T(n/8), but according to the problem, T(7n/8) has to be n log 8 n, even though I end up getting n log 7/8 n. How would I get n log 8 n from the T(7n/8)?

Also, I have no idea what I'm supposed to do with the 5n, so far I've only seen it as bn, does it change anything when the b is given? Or is the process more or less the same? Any help would be greatly appreciated.

Answer 1

The log base "8" is not required in big-O and big-Theta notation, because constant factors are ignored in big-O and big-Theta. The point is that you are keeping the total amount of "mass" (the sum of the arguments you pass into $T$) the same at each recursion depth because it's $n/8$ and $7n/8$ when you go from one level to the next, which adds up to $n$. As soon as that happens, you can prove that at each level of the recursion tree, you are adding the same amount of total contribution ($5n$ in this case where $n$ is the original value) to the value of $T$, and since you are reducing the arguments to $T$ by constant multiplicative factors at each level this implies that the total contribution is $O(n \log n)$ because you do $O(\log n)$ recursion depth before you reach the base case due to the multiplicative factors. (The inverse of exponential is logarithm).

This is all covered by the so-called "Master's Theorem" in Algorithm analysis. Are you familiar with it?