Master theorem: what to do with constant in parenthesis?

Question

In analysis of algorithms, we sometimes use the (unsimplified) Master Theorem for recurrence relations.

What should be done in the case that there is a constant factor in the numerator following T?

$$ T(n) = 2T\left(\frac{5n}{8}\right) + 1 $$

Does b simply equal $\frac{5}{8}$? This seems a contradiction to the Theorem.

Answer 1

Usually the general form of the recurrences solved by the Master theorem is stated as: $$ T(n) = aT\left(\frac{n}{b}\right) + f(n). $$

In your recurrence you have $a=2$, $b=\frac{8}{5}$, and $f(n)=1$.

Answer 2

Your confusion stems from the fact that the MT is often stated in the form $$T(n) = aT(n/b) + f(n),$$ so $b$ is expected to be some constant larger than 1. The recurrence relation you give is not in this form, so to rewrite it to fit the form you know, write $T(n) = 2T(n / (8 / 5)) + 1$ and take it from there.