Counting
Multiply, add, and only then throw constants away.
- Give every simple statement a constant cost \(c_i\).
- Count how many times it runs, as a function of \(N\).
- Multiply, add, and only then drop constants and lower-order terms.
- Sequential statements add.
- An if/else is charged the more expensive branch when you want one formula for every input.
- A loop’s cost is the sum of its iterations, not “about \(N\)”.
- A while-test runs one more time than the body. The last check is the one that fails.
The sums that keep showing up
\[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
\[ \sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} \]
\[ \sum_{i=0}^{n} 2^{i} = 2^{n+1}-1 \]
The triangle \(\sum_{i=1}^{N-1} i = N(N-1)/2\) is what selection sort always pays, and what insertion sort pays on reversed input.
A loop you should count cold
s = 0
k = 1
while (k <= N)
s = s + k
k = k + 1
The test runs \(N+1\) times. Each body line runs \(N\) times. So
\[ T(N) = (c_3+c_4+c_5)\,N + (c_1+c_2+c_3) = \Theta(N). \]
Nothing in the bounds depends on the data. Best, worst, and average are the same.
When the inner loop is a triangle
c = 0
for i = 0 to N-1
for j = 0 to i-1
c = c + 1
For a fixed \(i\), the inner body runs \(i\) times. The \(i = 0\) pass runs 0 times.
\[ \sum_{i=0}^{N-1} i = \frac{N(N-1)}{2}. \]
So the fragment is \(\Theta(N^2)\). Replacing the body with an if does not change the trip count. A break or a return would. That is why insertion sort has a best case and this loop does not.