2
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.