Common Running Times

Big-oh puts the amount of work an algorithm does, as the input size grows, into a family of functions that share a growth rate.

The amount of work an algorithm does affects how long it takes to run. We often use the terms running time and runtime to mean the amount of work an algorithm does, and we use faster and slower to compare the running times of two algorithms. The faster one does less work for large inputs, and the slower one does more.

Here are the common running time families, ordered from the slowest-growing at the top (faster running times) to the fastest-growing at the bottom (slower running times):

$O (1)$ , constant. The work does not depend on the input size at all. Reading an element by index, or swap, or appending to a DynamicArray. Remember that $O (1)$ does not mean one step, only a number of steps that stays fixed as $n$ grows.
$O (lo g n)$ , logarithmic. The work grows, but much more slowly than the input, because each step eliminates a constant fraction of what is left. Binary search is $O (lo g n)$ , and we will see other logarithmic algorithms later.
$O (n)$ , linear. The work is proportional to the input. Linear search, or any single pass over an array, like indexOfMin.
$O (n lo g n)$ , linearithmic. A little more than linear. The fastest general-purpose sorting algorithms are in this family. We will see them later.
$O (n^{2})$ , quadratic. The work is proportional to the square of the input. Selection sort is in this family. We will see other quadratic sorting algorithms later.
$O (n^{k})$ , polynomial. Any constant power $k > 1$ ; quadratic is just the case $k = 2$ . The cost grows quickly as $k$ grows.
$O (c^{n})$ , exponential. A constant raised to the input, so the work multiplies by roughly $c$ for each element added to the input. Trying every subset of $n$ items is $O (2^{n})$ .
$O (n!)$ , factorial. Trying every ordering of $n$ items. This is too slow for anything but very small $n$ .

These few families are enough to describe nearly every algorithm in this course, and most of the ones you would see in a coding interview. Given two algorithms, the one in the slower-growing family is the faster one for large $n$ .

As a rough guide:

Practically efficient (still usable on large inputs): $O (1)$ , $O (lo g n)$ , $O (n)$ , $O (n lo g n)$
Practically inefficient (too slow on large inputs): $O (n^{2})$ , $O (2^{n})$ , $O (n!)$