Week 5 - Problem solving

Problem solving methods

Basic algorithms

Big O notation

Logging

Debugging

Unit testing

AI

Practice

Assignment

Core program

Big O Notation

Big O notation is a way to describe how fast or slow an algorithm grows as the input gets larger.

It doesn’t measure time in seconds — instead, it measures how the number of operations increases as data grows.

Big O helps you answer questions like:

• Will this algorithm still work if the data gets 10× bigger?
• Is my solution efficient or slow?
• Which approach is better for large inputs?

💡 Big O is about patterns, not about measuring exact speed.

⚠️ You do not need math skills to understand Big O — just logic.

Why Big O matters

Real-world programs often handle huge amounts of data:

• social media feeds
• product lists
• messages
• files
• search results

Inefficient algorithms become slow as data grows.

Big O helps developers:

• compare solutions
• identify performance issues
• choose the right algorithm
• understand trade-offs

The most common Big O values

These patterns appear all the time in software development:

Let’s break these down.

O(1) – Constant Time

Algorithm does the same amount of work no matter the input size.

const first = array[0];    // Always one operation.

It doesn’t matter if the array has 5 items or 5 million — accessing an index is always O(1).

Input size:   1   10   1000   1,000,000
Work done:    1    1      1          1

💡 O(1) is the fastest time complexity.

O(n) – Linear Time

Work grows directly with input size — usually caused by a single loop.

for (let i = 0; i < array.length; i++) {
  console.log(array[i]);
}

If the array doubles in size, the work doubles.

Input size:   1   10   100   1000
Work done:    1   10   100   1000

Examples of O(n):

• searching through an unsorted list
• checking every item
• counting items that match a condition

💡 If you loop through the whole array once → O(n).

O(n²) – Quadratic Time

Usually caused by nested loops.

for (let i = 0; i < array.length; i++) {
  for (let j = 0; j < array.length; j++) {
    console.log(i, j);
  }
}

If the input doubles, the work becomes four times larger.

Input:     10 → 100 operations
Input:     20 → 400 operations
Input:     40 → 1600 operations

Examples:

• bubble sort
• comparing every item to every other item
• building a multiplication table

⚠️ O(n²) becomes slow very quickly. Avoid if possible.

O(log n) – Logarithmic Time

One of the fastest patterns.

The algorithm reduces the problem size dramatically at each step.

Example: Binary Search

Each step cuts the remaining data in half.

100 → 50 → 25 → 12 → 6 → 3 → 1

JavaScript example (simplified):

while (start <= end) {
  const middle = Math.floor((start + end) / 2);

  if (target === array[middle]) break;

  if (target < array[middle]) {
    end = middle - 1;
  } else {
    start = middle + 1;
  }
}

💡 O(log n) algorithms are extremely efficient and scale well.

O(n log n) – Linearithmic Time

Common in efficient sorting algorithms like:

• Merge Sort
• Quick Sort (average case)
• TimSort (JavaScript’s built-in .sort())

These split the data (log n) and process each piece (n).

You don’t need to fully understand sorting yet — just remember:

💡 O(n log n) is faster than O(n²) and used in most practical sorting.

Visual comparison (rough shapes)

Fastest → Slowest
O(1)        █
O(log n)    ██
O(n)        ███████
O(n log n)  ████████████
O(n²)       ████████████████████████████

Big O for common code patterns

Single loop

for (...) {}

→ O(n)

Nested loops

for (...) {
  for (...) {}
}

→ O(n²)

Accessing array index

arr[999];

→ O(1)

Looping then calling function inside loop

for (...) doSmallWork();

→ O(n) (assuming the function is O(1))

Looping then sorting

arr.sort();   // O(n log n)
for (...) {}  // O(n)

Total → O(n log n) (the dominant term)

💡 Big O only cares about the dominant term, not small details.

What Big O does not measure

• actual running time