0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Awesome, thanks! I found my notes on Master's Theorem and it helped a lot. $\endgroup$ Feb 5, 2015 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.