Math assumptions #

Created Thu May 9, 2024 at 7:42 AM

Bear in mind, therefore, that although asymptotic notation subsumes constant multiplicative factors, recursive notation such as T (n/2) does not.

Intuitively, our guess is nearly right: we are off only by the constant 1, a lower-order term. Nevertheless, mathematical induction does not work unless we prove the exact form of the inductive hypothesis.