Big O Notation in 1 minute

See also:

• 2 minutes explanation
• 5 minutes explanation
• 8 minutes explanation

Big O Notation is a mathematical function used in computer science to describe how complex an algorithm is.

There are two kinds of complexities: time and space.

Typically, there are three tiers (known as asymptotic notations) to solve for:

• Best case → Big Omega or Ω(n)
• Average case → Big Theta or Θ(n)
• Worst case → Big O or O(n)

O(1) – Constant time complexity

One single step.

OPs
|
|
|
|
|
| .  .  .  .  .  .  .
|
+----------------------------- Elements

O(log n) – Logarithmic time complexity

If it takes 1 second to compute 10 elements, it will take 2 seconds to compute 100.

OPs
|
|                                     . 
|                    . 
|           . 
|      . 
|   .
| .
+----------------------------- Elements

O(n) – Linear time complexity

Loop of n steps.

OPs
|                   .
|                . 
|             . 
|          . 
|       . 
|    .
| .
+----------------------------- Elements

O(n²) – Quadratic time complexity

Loop inside a loop.

OPs
|                  .
|                 . 
|               .  
|            . 
|         . 
|     .
| .
+----------------------------- Elements