In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-O. Is this always the case for Master Theorem and iteration method, respectively?

  • $\begingroup$ The master theorem gives big Theta bounds, see the Wikipedia version. $\endgroup$ Commented Feb 10, 2022 at 7:11
  • $\begingroup$ Sure, linked wikipedia article states for divide-and-conquer problems where the algorithm splits into two equal sizes, then MT provides tight bounds. However, throughout the article, big O is also used interchangeably. For example, in the last table ("Application to common algorithms"), all of the bounds are expressed in big O with no reference to big Theta $\endgroup$
    – There
    Commented Feb 10, 2022 at 18:50
  • $\begingroup$ It's for historical reasons. Big Theta was introduced much later, and it has become common to list running times using Big O. $\endgroup$ Commented Feb 10, 2022 at 21:17


Your Answer

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