Expressing Code in Big-O Notation: Solving Real-World Examples

Chris is reviewing code written by a colleague.

The variable names are clean, and the comments are well-written. But the loop structure feels somewhat odd.

"Hey, this function looks fine for 100 items, but if the data exceeds 10,000, I think the server might freeze."

"Huh? I only used one loop, why?"

Faced with his colleague's question, Chris had to explain with precise evidence.

"This looks like a single loop, but there's actually a hidden loop inside, making it O(N^2)!"

Today is a practical training session to apply the vague concept of Big-O to actual code and calculate it. If you can do addition and multiplication, anyone can do this.

1. The 4 Laws of Big-O Calculation

You don't need complex math formulas. Just scan the code with your eyes and apply these 4 rules.

Rule 1: Worst Case

There is no "I got lucky and found it immediately." Always assume "The data we are looking for is at the very end of the array."

Rule 2: Drop Constants

Whether you run a loop 2 times (2N) or 100 times (100N), in Big-O, it's just O(N).

As N grows to infinity, a difference of 2x or 100x does not affect the slope (trend) of the graph.

Rule 3: Drop Non-Dominants

O(N^2 + N + 10) \rightarrow O(N^2)

Compared to the speed at which N^2 grows, N or 10 is like dust. Keep only the most powerful term.

Rule 4: Add Up Step-by-Step Operations

Add up the cost of each line of code.

Simple assignment (=), arithmetic operations (+), and comparison (>) are O(1).

2. Analyzing Real Examples

Example 1: Addition (Ignore Constants)

function printCount(n) {
  for (let i = 0; i < n; i++) { // Repeats n times
    console.log(i);
  }

  for (let j = 0; j < n; j++) { // Repeats n times
    console.log(j);
  }
}

Example 2: Multiplication (Nested Loops)

function printPairs(n) {
  for (let i = 0; i < n; i++) {       // Repeats n times
    for (let j = 0; j < n; j++) {   // Repeats n times inside
      console.log(i, j);
    }
  }
}

Every time the outer loop runs once, the inner loop runs N times.

Example 3: Different Inputs (N vs M)

function processItems(arr1, arr2) {
  arr1.forEach(item => console.log(item)); // Repeats a times
  arr2.forEach(item => console.log(item)); // Repeats b times
}

Since the input arrays are different, you can't just lump them as N.

3. Chris's Point: Finding Hidden Complexity

Now let's look at the colleague's code Chris pointed out. There is definitely only one loop.

// ⚠️ Trap Card Activated
function findCommon(arr1, arr2) {
  // Iterate through arr1 (N times)
  arr1.forEach(item1 => {
    // Check if item1 exists in arr2 (includes)
    if (arr2.includes(item1)) { 
      console.log("Found:", item1);
    }
  });
}

Why is this code O(N^2)?

The culprit is the includes() method.

As we learned in Part 1, JavaScript's includes, indexOf, slice, etc., are internally loops that scan the array from beginning to end (O(N)).

So, this code is exactly the same as having a for loop inside a for loop.

Solution:

If you convert arr2 to a Set (Hash Table) or Object, you can reduce the search to O(1). Then the total complexity drops to O(N). This is the basic pattern of algorithm optimization.

4. Wrapping Up Chapter 1: Algorithmic Mindset Equipped

So far, we have built up our basic algorithmic stamina.

Now, Chris is not satisfied with simply making code "work."

He has become an engineer who asks, "What if there are 1 million items?" and considers better logic by weighing time and space efficiency.

From the next chapter, it's time to collect serious weapons.

Simply arranging data in order can drastically increase search speed. Let's depart for the world of Sorting Algorithms, a regular guest in developer interviews.

Continuing in: "Sorting Algorithms."

🔗 References