# The Big O Notation

16 Aug 2020  Sergio Martin Rubio  2 mins read.

O-notation (pronounced big-oh notation) is a way of describing the performance of an algorithm and provides an upper bound or worst case on a function. Using O-notation you can describe the running time of an algorithm by inspecting its structure.

## Upper, Lower and Tight Bound

• Lower bound ($$\Omega$$) functions are those that stay below $$T(n)$$ given a constant $$c$$, that is, $$T(n)\leq c n$$ for all $$n > 0$$. In other words, lower bounding is about finding a function that given a $$c$$ value always stays below $$T(n)$$. e.g. given a quadratic function $$T(n)=n^2$$ a lower bound function would be $$f(n)=nlog(n)$$.

• Upper bound ($$O$$) functions are those that stay above $$T(n)$$ given a constant $$c$$, that is, $$T(n)\geq cn$$ for all $$n > 0$$. In other words, upper bounding is about finding a function that given a $$c$$ value always stays above $$T(n)$$. e.g. given a linear function $$T(n) = n$$ an upper bound function would be $$f(n)=n^2$$.

• Tight bound or exact bound ($$\Theta$$) is a combination of lower bound and upper bound. In other words, it’s a function that bound $$T(n)$$ from the top and from the bottom. Tight bound functions are those that stay us much close as possible to $$T(n)$$ given a constant $$c$$, that is, $$T(n)\approx cn$$ for all $$n > 0$$. e.g. given a linear function $$T(n) = n$$ a tight bound function would be $$f(n) = n$$, since we were able to choose a value $$c$$ that satisfy the lower bound, $$f(n) = \frac12n$$ and a value $$c$$ that satisfy the upper bound, $$f(n) = 100n$$. As a result, we could find a value $$c$$ that can serve as an exact bound ($$\Theta(n)$$) for this function.

IMPORTANT: When we talk about time complexity we usually use $$O$$ as $$\Theta$$

## Running Time Cases

Algorithms can be classified by three running time cases:

• Worst case: This is the worst runtime behavior. The execution time upper bound uses the notation $$O(f(n))$$.
• Average case: This is the expected behavior given random input data.
• Best case: This is how an algorithm performs in an ideal situation. This is also called as the lower bound and the notation used is this case is $$\Omega(f(n))$$

## Performance Categories

O-Notation Name Example
$$O(1)$$ Constant Get in a hash map
$$O(log(n))$$ Logarithmic Binary Search
$$O(n)$$ Linear Linear Search
$$O(n log(n))$$ Linearithmic Merge Sort
$$O(n^2)$$ Quadratic Bubble Sort
$$O(2^n)$$ Exponential Recursive Fibonacci

Image by Free-Photos from Pixabay