My book says that the total number of leaves on the bottom level equals n^(log a / log b), with T(n) = a * T(n / b) + f(n). How do they come up with this?
Say I have a function 3 * T(n / 4) + f(n) (Example from the book). It says that the total leaves on the bottom level equals n^(log 3 / log 4).
Here is the formula I came up with:
Every level, the leaves increase by a multiple of 3. So the amount of leaves at a certain level must be 3^level. The bottom level will be reached when n / b = 1. Since b gets divided at each level, the amount of levels is given by log(n) / log(b). This gives the formula: 3^(log n / log b). Does this equal n^(log 3 / log 4), or am I doing something wrong?
If you have a formula: $$T(n) = a \cdot T(n/b) + f(n)$$ then number of leaves will be $a^{\log_b{n}}$, which is equal to $n^{log_b{a}}$ according to the Logarithm Change of Base Formula: $$log_y{x} = \dfrac {log_z{x}} {log_z{y}}$$ So, you can change the base in the $\log_b{n}$: $$log_b{n} = log_a{n} \cdot log_b{a}$$ Your calculations are basically correct, you only didn't do the last step.
(Also, please use MathJax in your questions on this site)