# Swift Algorithm Series: Big O Notation

## What is Big O Notation?

Big O notation is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions.

Basically, it tells you how fast a function grows or declines.

We can express complexity using Big O Notation.

For a problem of size n:

- a constant-time algorithm is “order 1”: O(1)
- a linear-time algorithm is “order n”: O(n)
- a quadratic-time algorithm is “order n squared”: O(n^2)

### O(1)

Name: constant

Rating: **This is the best.**

Description: The algorithm always takes the same amount of time, regardless of how much data there is.

Example: Looking up an element of an array by its index

### O(log n)

Name: logarithmic

Rating: **Pretty great.**

Description: These kinds of algorithms halve the amount of data with each iteration. If you have 100 items, it takes about 7 steps to find the answer. With 1,000 items, it takes 10 steps. And 1,000,000 items only take 20 steps. This is super fast even for large amounts of data.

Example: Binary Search

### O(n)

Name: linear

Rating: **Good performance.**

Description: If you have 100 items, this does 100 units of work. Doubling the number of items makes the algorithm take exactly twice as long (200 units of work).

Example: Linear Search

### O(n log n)

Name: linearithmic

Rating: **Decent performance.**

Description: This is slightly worse than linear but not too bad.

Example: Quicksort | Merge Sort

### O(n^2)

Name: quadratic

Rating: **Kinda slow.**

Description: If you have 100 items, this does 100^2 = 10,000 units of work. Doubling the number of items makes it four times slower (because 2 squared equals 4).

Example: Insertion Sort | Bubble Sort

### O(n^3)

Name: cubic

Rating: **Poor performance.**

Description: If you have 100 items, this does 100^3 = 1,000,000 units of work. Doubling the input size makes it eight times slower.

### O(2^n)

Name: exponential

Rating: **Very poor performance.**

Description: You want to avoid these kinds of algorithms, but sometimes you have no choice. Adding just one bit to the input doubles the running time.

### O(n!)

Name: factorial

Rating: **Intolerably slow.**

Description: It literally takes a million years to do anything.

## References

Swift Algorithm & Data Structures Book