Time and space complexity explained with one practical example

Suppose a signup form receives a list of usernames from an imported spreadsheet. Before creating accounts, you need to answer one simple question:

Does this list contain any duplicate username?

For 20 usernames, almost any correct solution feels instant. For 200,000 usernames, the wrong solution can become painfully slow or use more memory than expected. Time and space complexity help you predict that behavior before the code reaches production.

By the end of this guide, you will be able to read simple code, estimate its Big O time, estimate its extra space, and explain why two correct solutions can behave very differently as input grows.

The mental model: count growth, not seconds

Time complexity describes how the amount of work grows when the input grows. Space complexity describes how much extra memory the algorithm needs as the input grows.

The input size is usually written as n. In our example, n means the number of usernames in the list.

Big O notation does not try to predict exact runtime in milliseconds. Exact runtime depends on hardware, language, compiler, database, network, and many other details. Big O asks a narrower question:

When n becomes large, which part of the work grows fastest?

That is why complexity analysis ignores small constants and lower-order terms. It is a simplified model, but it is useful because it focuses your attention on growth.

A first solution: compare every pair

The most direct way to find duplicates is to compare each username with every username after it.

function hasDuplicateUsername(usernames: string[]) {
  for (let i = 0; i < usernames.length; i++) {
    for (let j = i + 1; j < usernames.length; j++) {
      if (usernames[i] === usernames[j]) {
        return true;
      }
    }
  }

  return false;
}

This code is correct. If any duplicate pair exists, it eventually finds it.

Now count the comparisons in the worst case. The worst case happens when there is no duplicate, or when the duplicate appears very late. For n usernames:

The first username is compared with n - 1 later usernames.
The second username is compared with n - 2 later usernames.
The third username is compared with n - 3 later usernames.

The total is:

(n - 1) + (n - 2) + ... + 1

That grows roughly like n * n / 2, so the time complexity is O(n^2).

The function uses only a few variables: i, j, and the existing input array. It does not create another data structure that grows with n, so its extra space complexity is O(1).

This is the first important tradeoff:

Pair comparison solution: O(n^2) time, O(1) extra space

It saves memory, but it can be very slow for large lists.

Why O(n^2) grows so quickly

Quadratic growth is easy to underestimate.

Number of usernames	Approximate pair comparisons
100	4,950
1,000	499,500
10,000	49,995,000
100,000	4,999,950,000

When the input becomes 10 times larger, the work becomes about 100 times larger. That is the practical meaning of O(n^2).

The code did not become less correct. The input size exposed the cost of the approach.

A faster solution: remember what you have seen

Instead of comparing every pair, store usernames as you scan the list. If you see a username that is already stored, you found a duplicate.

function hasDuplicateUsername(usernames: string[]) {
  const seen = new Set<string>();

  for (const username of usernames) {
    if (seen.has(username)) {
      return true;
    }

    seen.add(username);
  }

  return false;
}

This version usually checks each username once. Set.has and Set.add are commonly treated as constant-time operations on average for this kind of analysis.

The time complexity is O(n) because the loop grows directly with the number of usernames.

The extra space complexity is O(n) because the seen set can store up to n usernames when there are no duplicates.

Set solution: O(n) time, O(n) extra space

This is often the better production choice for large input because it trades memory for speed. It is not "always better"; it is better when the extra memory is acceptable and the list can be large enough for quadratic time to hurt.

Same problem, different tradeoff: sort first

There is another common strategy. If duplicate usernames exist, equal values will sit next to each other after sorting.

function hasDuplicateUsername(usernames: string[]) {
  const sorted = [...usernames].sort();

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) {
      return true;
    }
  }

  return false;
}

This code has two phases:

Copy and sort the usernames.
Scan the sorted list once.

The scan is O(n). The sort is usually O(n log n) for general-purpose comparison sorting. The total becomes:

O(n log n) + O(n)

Big O keeps the fastest-growing term, so the time complexity is O(n log n).

The extra space is O(n) because [...usernames] creates a copy. Depending on the language and sorting implementation, sorting itself may also need extra memory. For beginner analysis, it is enough to say this version uses extra memory that grows with n.

Sort-and-scan solution: O(n log n) time, O(n) extra space

Why use it if the Set solution is faster? Sometimes sorted output is useful for another step. Sometimes you want deterministic grouping. Sometimes memory or platform details change the decision. Complexity is not a rule that chooses the algorithm for you; it gives you the vocabulary to compare choices.

Common time complexities in one table

Use this table as a recognition guide, not as something to memorize mechanically.

Complexity	Name	Typical pattern	Example question
O(1)	Constant	Do a fixed amount of work	Read `usernames[0]`
O(log n)	Logarithmic	Cut the search space each step	Binary search in sorted usernames
O(n)	Linear	Visit each item once	Scan all usernames
O(n log n)	Linearithmic	Sort or divide-and-combine efficiently	Sort usernames, then scan
O(n^2)	Quadratic	Compare many pairs	Nested pair comparison

Where O(log n) fits

Logarithmic time appears when each step removes a large part of the remaining work.

If usernames are already sorted, you can check whether one username exists using binary search:

function containsUsername(sortedUsernames: string[], target: string) {
  let left = 0;
  let right = sortedUsernames.length - 1;

  while (left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (sortedUsernames[middle] === target) return true;

    if (sortedUsernames[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return false;
}

Every loop cuts the remaining search range roughly in half. That gives O(log n) time and O(1) extra space.

This does not mean binary search solves every problem. It requires sorted data and a question that can eliminate half the search space safely. If the data is unsorted, you must account for the cost of sorting first.

Quick check

A function scans a list once and stores each visited value in a Set. What are the usual time and extra space complexities?

How to analyze a piece of code

Use this process when you see a new function:

Define n.
Identify the repeated work.
Count how many times that work can happen in the worst case.
Keep the dominant growth term.
Count extra memory separately.

For our first duplicate-checking function:

n is the number of usernames.
The repeated work is a comparison.
The worst case compares many pairs.
Pair comparisons grow as n^2.
Only a few loop variables are allocated.

So the result is O(n^2) time and O(1) extra space.

For the Set version:

n is still the number of usernames.
The repeated work is checking and inserting into the set.
Each username is processed once.
The set can grow to n items.

So the result is O(n) time and O(n) extra space.

Mistakes beginners often make

Counting loops without understanding them: Nested loops often mean O(n^2), but not always. If two pointers move forward through the same list and never move backward, the total work may still be O(n).

Forgetting the cost of helper methods: A line like array.includes(value) inside a loop can hide another scan. That can turn code that looks linear into quadratic code.

function hasDuplicateUsername(usernames: string[]) {
  const seen: string[] = [];

  for (const username of usernames) {
    if (seen.includes(username)) {
      return true;
    }

    seen.push(username);
  }

  return false;
}

This looks like one loop, but seen.includes(username) scans the seen array. In the worst case, the total work grows like pair comparison: O(n^2).

Mixing time and space into one answer: "This is O(n)" is incomplete if the question asks for both. Say "O(n) time and O(n) extra space" or "O(n) time and O(1) extra space."

Ignoring input size: For very small inputs, the simplest correct solution may be fine. Complexity matters most when input size can grow.

Assuming Big O measures everything: Big O does not replace benchmarking. It helps you choose what is worth measuring and which algorithm is likely to scale.

Space complexity includes new memory, not the input itself

When we say "extra space," we usually do not count the input array that was already given to the function. We count additional memory the algorithm allocates.

function firstUsername(usernames: string[]) {
  return usernames[0];
}

This is O(1) extra space. It does not copy the list.

function copyUsernames(usernames: string[]) {
  return [...usernames];
}

This is O(n) extra space because the returned array grows with the input.

Recursive functions can also use extra space through the call stack. If a recursive function goes n calls deep, its stack space is usually O(n). If it repeatedly splits the problem in half and the deepest path has log n calls, the stack space may be O(log n).

Choosing between correct solutions

For duplicate usernames, the three solutions give different tradeoffs:

Approach	Time	Extra space	When it may make sense
Compare every pair	O(n^2)	O(1)	Tiny lists or strict memory limits
Use a Set	O(n)	O(n)	Large lists when memory is acceptable
Sort, then scan	O(n log n)	O(n)	When sorted data is also useful

The best solution depends on constraints. In most application code, the Set version is a strong default for duplicate detection because it is simple and linear. In an interview, explain the tradeoff rather than just naming the Big O.

Practical summary

Time complexity asks how work grows. Space complexity asks how extra memory grows. Big O ignores constant details so you can focus on the dominant growth pattern.

For analysis, do not start by memorizing formulas. Start with a concrete question:

What is n?
What operation repeats?
Does the code scan, halve, sort, or compare pairs?
What new memory grows with the input?

Small challenge: write the duplicate-username problem in your preferred language using all three approaches: pair comparison, Set, and sort-and-scan. Then test each one with 100, 10,000, and 100,000 generated usernames. The exact timings will vary, but the growth pattern will make Big O feel real.