# 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( n) ∊ O(f(n))**, and say that T(

*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

_{0}.

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_{0} such that T(*n*) ≤ M when *n* ≥ n_{0}. 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( n) ∊ Ω(f(n))**, and say that T(

*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.