Data Structures & Algorithms·Reason about cost and structure

Complexity and Big O

Big O describes how work grows, not how many milliseconds a machine takes.

Intermediate 13 min read Lesson 6 of 300 Challenge included

What you will be able to do

State the variable you are measuring, usually n.
Consider both time and auxiliary space.
A smaller growth class wins on large inputs, not always on tiny ones.

In plain English

Count the dominant operation as input size grows. O(1) is constant, O(log n) halves the problem, O(n) touches each item and O(n²) compares pairs. Drop constants and lower-order terms; keep the growth class.

complexity.jsJavaScript

// O(n): one pass
function total(values) {
  let sum = 0
  for (const value of values) sum += value
  return sum
}

// O(n^2): compare every pair
function hasDuplicate(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
}

Your turn

Improve duplicate detection

Medium

Replace the O(n²) duplicate check with an O(n) Set-based implementation.

JS · starter

function hasDuplicate(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
}

Check your understanding before moving on.

Knowledge checkQuestion 1

What is the complexity of comparing every pair in an array?

Select an answer to continue

Study tools

Make it yours.

Keep a private note for this lesson, then turn the key ideas into flashcards you can revisit.

Sign in to save notes and flashcards.Both are private to your account and stay with your progress.

Finished reading?

Lock in what you just learned.

Mark this lesson complete to save your place and move one step closer to the certificate.

Next: Arrays, strings and two pointers

Lesson 6 of 300 · 0% of course