Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n)
Bottom-up heap construction. Choose one application of sift-down as your unit of measurement. Then the recurrence is $T(n) = T(n/2) + n$.

If you want to go beyond that, you can say that choosing sift-down as a unit for measurement isn't quite accurate, and its runtime depends on the height $h$ of heap being sifted down in. But you can show that bottom-up heap construction is still $O(n)$ due to

$$0\cdot n + 1\cdot \frac{n}{2} + 2\cdot \frac{n}{4} + \cdots + h\cdot 1 = \sum_{h=0}^{\lg n} h\frac{n}{2^h} &lt; n\sum_{h=0}^\infty \frac{h}{2^h}$$

and showing (or simply stating without proof in case you feel the students are not ready yet) that $\sum_{h=0}^\infty \frac{h}{2^h}$ converges to a constant.