analysis

Big O Notation

Big O Notation is a mathematical notation used in computer science to describe the performance or complexity of an algorithm. Specifically, it describes the worst-case scenario and can be used to describe the execution time or space requirements of an algorithm.

The "O" in Big O notation stands for "Order of," which indicates the rate of growth of an algorithm. This notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

When analyzing algorithms, we're primarily concerned with how they scale - that is, how their performance changes as the input size grows. Big O notation allows us to express this relationship mathematically, ignoring constants and lower-order terms that become insignificant with large inputs.

Common Big O Complexities (from fastest to slowest):

O(1) - Constant time: The operation takes the same amount of time regardless of the input size
O(log n) - Logarithmic time: Time increases logarithmically with input size
O(n) - Linear time: Time increases linearly with input size
O(n log n) - Linearithmic time: Common for efficient sorting algorithms
O(n²) - Quadratic time: Often seen in algorithms with nested loops
O(n³) - Cubic time: Typically found in algorithms with three nested loops
O(2^n) - Exponential time: Each additional element doubles the processing time
O(n!) - Factorial time: Used in algorithms that generate all permutations

Code Example

// O(1) - Constant time
function getFirstElement(array) {
  return array[0];
}

// O(n) - Linear time
function findMax(array) {
  let max = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }
  return max;
}

// O(n²) - Quadratic time
function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

Visual Explanation

Growth Rate Comparison

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

O(2^n)

O(n!)

Further Learning

Want to see these concepts in action?

Explore Sorting Algorithms Explore Searching Algorithms Explore Graph Algorithms

Big O Notation

Big O Notation

Common Big O Complexities (from fastest to slowest):

Code Example

Visual Explanation

Growth Rate Comparison

Related Terms

Time Complexity

Space Complexity

Asymptotic Analysis

Algorithm

Further Learning