In the world of high-scale engineering, "working code" isn't enough. It must be efficient. Time complexity helps us predict how an algorithm's runtime grows as the input size ($n$) increases.

Imagine you're looking for a specific toy in a box:

• O(1): You know exactly where it is. You grab it instantly, regardless of how many toys are in the box.
• O(n): You have to look at every single toy in the box until you find yours. If the box doubles in size, it takes twice as long.
• O(log n): You have a sorted pile. You look at the middle, discard half, and repeat. You find it very fast even in huge piles.

---

Big O Notation

Big O notation provides an upper bound on the time requirements of an algorithm. It focuses on the worst-case scenario.

Why Drop Constants?

We care about the growth rate. $O(2n)$ and $O(100n)$ both grow linearly. As $n$ approaches infinity, the constant factor becomes insignificant compared to the impact of $n$.

---

javascript Standard
/**
 * O(1) - Constant Time
 * It doesn't matter if the array has 10 or 1 million items.
 */
function getFirstItem(items) {
  return items[0]; // One operation
}

/**
 * O(n) - Linear Time
 * The runtime grows directly with the size of the array.
 */
function findItem(items, target) {
  for (let item of items) {
    if (item === target) return true;
  }
  return false;
}

/**
 * O(n²) - Quadratic Time
 * Common in "Brute Force" solutions involving nested loops.
 */
function hasDuplicate(items) {
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (items[i] === items[j]) return true;
    }
  }
  return false;
}

---

Common Patterns

1. Halving the search space: Usually indicates O(log n).
2. One loop: Usually O(n).
3. Nested loops: Usually O(n²).
4. Dividing and then looping: Often indicates O(n log n).

Pro-Tip

Always start with the most intuitive (often O(n²)) solution in an interview, then explain how you'll use a better data structure (like a HashMap) to bring it down to O(n).