Skip to content

Big-O

Big-O is a notation used to describe how well an algorithm performs.

It describes the time complexity of an algorithm as the number of inputs to that algorithm increases.

Definition: "Simplified analysis of an algorithm's efficiency."

The Premise

You usually see Big-O notation as O(n)

  • The O stands for Order of complexity
  • The n stands for the number of inputs.

As we add more inputs to the algorithm, there are two things that can potentially grow in complexity.

  • Time complexity: It may take longer to run the algorithm as more inputs are added.
  • Space complexity: It may require more space to compute the algorithm.

Overview

An overview of the typical Big-O notations:

  • O(log n): Logarithmic complexity.
    • The complexity scales by the logarithm of the number of inputs.
    • E.g., a binary search function over an array.
  • O(n): Linear complexity.
    • The complexity scales with a 1:1 ratio to the number of inputs.
    • E.g., looping over the elements of an array.
  • O(n²): Quadratic complexity.
    • The complexity scales with a 1:1² ratio to the number of inputs.
    • This happens with nested for loops while looping over two separate arrays.
  • O(2ⁿ): Exponential complexity.
    • The complexity scales exponentially with the number of inputs.
  • O(1): Constant complexity.
    • It will always take the same amount of time.
    • E.g., looking up an element of an array by its index.