Rekursjonstre: arbeid på hvert nivå

Hvordan vet vi at en del-og-hersk-algoritme bruker n ganger log n? Vi bretter rekursjonen ut som et tre, leser av arbeidet i hver node, og oppdager at hver rad summerer til n. Roten gjør n arbeid. To barn med n delt på to. Fire barnebarn med n delt på fire. Helt ned til løvene på ett. Treet er log av n nivåer dypt — og hvert nivå koster n. Sum: n ganger log n. Det er motoren bak flettesortering, hurtigsort, og hver eneste splitt-og-hersk-algoritme i pensum.