What is Big O notation and how is it used in programming?

Big O notation describes the upper bound of an algorithm's running time or memory usage depending on the input size (n). It allows estimating the scalability of an algorithm as the input size grows. It is used to compare the efficiency of algorithms and select the most suitable solution for a specific task.

Common complexity classes:

• O(1): Constant time. The execution time does not depend on the input size.
• O(log n): Logarithmic time. The execution time grows slower than the input size (e.g., binary search).
• O(n): Linear time. The execution time is directly proportional to the input size (e.g., simple array traversal).
• O(n log n): Linear-logarithmic time. Common in efficient sorting algorithms (e.g., quicksort, merge sort).
• O(n^2): Quadratic time. The execution time is proportional to the square of the input size (e.g., bubble sort).
• O(2^n): Exponential time. The execution time grows very rapidly with increasing input size (often in subset enumeration problems).

Examples:

Array traversal:

// O(n)
function findElement(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return true;
    }
  }
  return false;
}

Binary search:

// O(log n)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Comparison table of growth:

O-notation	Name	Growth when n increases	Example
O(1)	Constant	Slow (no growth)	Index access
O(log n)	Logarithmic	Slow	Binary search
O(n)	Linear	Moderate	Array traversal
O(n log n)	Linear-logarithmic	Average	Quick sort
O(n^2)	Quadratic	Fast	Bubble sort
O(2^n)	Exponential	Very fast	Subset enumeration