# Big O notation explained

Big O notation is a convenient way to describe how fast a function is growing.

When studying the time complexity T(*n*) of an algorithm
it’s rarely meaningful, or even possible, to compute an exact result.
Typically we are only interested in how fast T(*n*) is growing
as a function of the input size *n*.

For example, if an algorithm increments each number in a list of length *n*,
we might say: “This algorithm runs in O(*n*) time and performs O(1) work for each element”.

**Definition:**Let T(

*n*) and f(

*n*) be two positive functions. We write

**T(**, and say that T(

*n*) ∊*O*(f(*n*))*n*) has order of f(

*n*), if there are positive constants M and n₀ such that T(

*n*) ≤ M·f(

*n*) for all

*n*≥ n₀.

Basically, T(*n*) ∊ *O*(f(*n*)) means that
T(*n*) doesn’t grow faster than f(*n*).

## Constant time

Let’s start with the simplest possible example: **T( n) ∊ O(1)**.

According to the definition this means that there are constants M and n₀
such that T(*n*) ≤ M when
*n* ≥ n₀.
In other words, T(*n*) ∊ *O*(1) means that
T(*n*) is smaller than some fixed constants, whose value isn’t stated,
for all large enough values of *n*.

An algorithm with T(*n*) ∊ *O*(1) is said to have
**constant time complexity**.

## Linear time

In Time complexity explained
we looked at an algorithm `max`

with time complexity
T(*n*) = *n* -1.
Using Big O notation this can be written as **T( n) ∊ O(n)**.
(If we choose M = 1 and n₀ = 1, then
T(

*n*) =

*n*- 1 ≤ 1·

*n*when

*n*≥ 1.)

An algorithm with T(*n*) ∊ *O*(*n*) is said to have
**linear time complexity**.

## Quadratic time

The algorithm `reverse`

from
Time complexity explained
had time complexity T(*n*) = *n*^{2}/2 - *n*/2.
With Big O notation, this becomes
**T( n) ∊ O(n^{2})**, and we say
that the algorithm has

**quadratic time complexity**.

## Sloppy notation

The notation T(*n*) ∊ *O*(f(*n*)) can be used even when
f(*n*) grows **much faster** than T(*n*). For example, we may write
T(*n*) = *n* - 1 ∊ *O*(*n*^{2}).
This is indeed true, but not very useful.

## Ω and Θ notation

**Big Omega** is used to give a **lower bound** for the growth of a function.
It’s defined in the same way as Big O, but with the inequality sign turned around:

**Definition:**Let T(

*n*) and f(

*n*) be two positive functions We write

**T(**, and say that T(

*n*) ∊ Ω(f(*n*))*n*) is big omega of f(

*n*), if there are positive constants m and n₀ such that T(

*n*) ≥ m(f(

*n*)) for all

*n*≥ n₀.

**Big Theta** is used to indicate that an function is bounded both from above and below:

**Definition:**T(

*n*): ∊ Θ(f(

*n*)) if T(

*n*) is both

*O*(f(

*n*)) and Ω(f(

*n*)).

**Example:**

T(

n) = 3n^{3}+ 2n+ 7 ∊ Θ(n^{3})

- If
n≥ 1, then T(n) = 3n^{3}+ 2n+ 7 ≤ 3n^{3}+ 2n^{3}+ 7n^{3}= 12n^{3}. Hence T(n) ∊O(n^{3}).- On the other hand, T(
n) = 3n^{3}+ 2n+ 7 >n^{3}for all positiven. Therefore T(n) ∊ Ω(n^{3}).- And consequently T(
n) ∊ Θ(n^{3}).

## Key takeaways

When analyzing algorithms you often encounter the following time complexities (in order of growth):

- Θ(1)
- Θ(log
*n*) - Θ(
*n*) - Θ(
*n*log*n*) - Θ(
*n*^{k}), where k ≥ 2 - Θ(k
^{n}), where k ≥ 2 - Θ(
*n*!)

The first four indicate an excellent algorithm:

O(nlogn) is really goodAn algorithm with worst-case time complexity W(

n) ∊O(nlogn) scales very well. The logarithm function grows very slowly:

- log
_{2}1,000 ≈ 10,- log
_{2}1,000,000 ≈ 20,- log
_{2}1,000,000,000 ≈ 30.In fact,

O(nlogn) time complexity is close to linear: it takes roughly twice the time to solve a problem twice as big.

The last three typically spell trouble:

Ω(n^{2}) is pretty badAlgorithms with time complexity Ω(

n^{2}) are useful only for small input:nshouldn’t be more than a few thousand:

- 10,000
^{2}= 100,000,000.An algorithm with quadratic time complexity scales poorly: if you increase the input size by a factor 10, the time increases by a factor 100.

## Comments