If $T(n) = T\left(\frac{n}{2}\right) + 5$ (binary search), then the runtime in Big-O notation is $O(\log(n))$.

If $T(n) = T\left(\frac{n}{2}\right) + 0$, then is it correct to say that the the runtime in Big-O notation is $O(1)$?

Normally, one would need to recursively calculate $T\left(\frac{n}{2}\right)$, but since the constant is 0, the whole thing can be optimized to $T(n) = 0$.

  • 1
    $\begingroup$ Have you tried proving your claim? $\endgroup$ – Yuval Filmus Feb 28 at 19:42

Your Answer

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

Browse other questions tagged or ask your own question.