Lesson 2

When \(T(n)\) is the runtime of an algorithm on input of size \(n\), the following assumptions are usually made:

1. We are interested not in the explicit formula for \(T(n)\) but in its growth rate (or asymptotic behavior).
2. For this reason, we do not specify the initial conditions for \(T(n)\): in any case, if \(n\) is bounded above by some constant, then \(T(n)\) is also bounded by a constant.
3. When we write \(T(n/2)\), we implicitly assume that \(n\) is divisible by two (without this assumption, we would need to write \(T(\lceil n/2 \rceil)\)). This assumption is almost always easy to justify as follows: ensure beforehand that \(n\) is a power of two; to achieve this, \(n\) needs to be increased by at most a factor of two (e.g., if the input to the algorithm is an array of length \(40\), add dummy elements to the array and treat it as an array of length \(64\)). This eliminates fractional terms in the analysis.