The
O
(
n
) calculation is performed log
n
times.