What is Big O notation and why does it matter?

Big O answers one question: when the input gets larger, how does the work grow? A function that doubles its work when the input doubles is linear. A function with nested iterations over the same input is quadratic. Constants and small terms are dropped because they stop mattering as the input becomes large.

The growth rates you should recognise

• O(1): constant time, such as reading an array index
• O(log n): halving the search space, such as binary search
• O(n): one pass over the input
• O(n log n): comparison sorting
• O(n^2): nested loops over the same input
• O(2^n): exploring every subset

function containsDuplicate(values) {
  for (let i = 0; i < values.length; i++) {
    for (let j = i + 1; j < values.length; j++) {
      if (values[i] === values[j]) return true;
    }
  }
  return false;
}

You can often improve the complexity by changing the data structure. A hash set turns the duplicate check into one pass, giving O(n) time at the cost of O(n) space. That trade-off is usually the real interview discussion.