Should the $a$ and $b$ in Master theorem be integers or they can be rational numbers? I think $a$ must be an integer but $b$ can be rational.

  • $\begingroup$ I don't see a problem in them being rational (or even irrational) numbers. That being said, you will probably never really need to use this case (since in realistic algorithms $a$ and $b$ are whole numbers). Still, I'm not 100% sure that you can use this theorem when they are rational or irrational numbers, so please don't take that as granted. $\endgroup$
    – nir shahar
    Jul 4, 2021 at 9:48
  • 4
    $\begingroup$ They don't have to be integers. The proofs go through for any constant $a>0$ and $b>1$. $\endgroup$ Jul 4, 2021 at 10:39
  • $\begingroup$ @YuvalFilmus Thanks. $\endgroup$
    – Emad
    Jul 4, 2021 at 11:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.