The Big O Notation

Introduction

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

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:

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