From a Step Count to Big-Oh

Solution

Expression	Big-Oh
$7 n + 12$	$O (n)$
$4 n^{2} + 30 n + 9$	$O (n^{2})$
$n + 5 lo g n$	$O (n)$
$3 n lo g n + 8 n + 2$	$O (n lo g n)$
$500$	$O (1)$

In each case, set every coefficient to $1$ and keep only the term that grows fastest.

Solution

The two parts run one after the other, so the costs add: $O (n + lo g n)$ , which is $O (n)$ .

We may drop $lo g n$ because it grows more slowly than $n$ : as $n$ grows, $lo g n$ becomes a smaller and smaller fraction of $n + lo g n$ , so it does not change how the work grows.