Every solution you write has two questions attached to it: does it produce the correct answer, and does it produce it fast enough?

The second question is answered by time complexity. It is the tool that tells you whether your solution will finish in a fraction of a second or take longer than the age of the universe, depending on the size of the input.

Understanding time complexity is not optional in Data Structures and Algorithms. It is the foundation of every optimization decision you will ever make.

1. Concept

What is time complexity?

Time complexity is a way of describing how the runtime of an algorithm grows as the size of its input grows.

It does not measure actual clock time in milliseconds. It measures the relationship between input size and the number of operations your algorithm performs. This matters because clock time depends on hardware, language, and environment. The number of operations is a property of the algorithm itself.

We express time complexity using Big O notation. Big O describes the upper bound — the worst-case growth rate — of an algorithm's runtime.

When we say an algorithm is O(n), we mean: as the input grows by a factor of k, the number of operations grows by roughly the same factor k. When we say O(n^2), we mean: doubling the input roughly quadruples the operations.

Why it exists

Consider two solutions to the same problem. Both are correct. One uses a nested loop. One uses a hash map.

On an input of 10 elements, both finish instantly. On an input of 1,000,000 elements, one finishes in milliseconds and the other runs for hours. Time complexity is what tells you this before you run either solution.

In DSA, you are expected to analyze the complexity of your solution, explain it, and when possible optimize it. A correct solution that is too slow is not an acceptable solution.

Where it fits

Time complexity analysis belongs at two points in your problem-solving process:

1. During planning: estimate whether your approach is fast enough before writing code
2. After coding: confirm the complexity of what you wrote and consider whether it can be improved

2. Real-world Intuition

Imagine you are searching for a name in a phone book.

Approach 1: Start at the first page and read every name until you find it. If the phone book has 1,000 pages and the name is on page 999, you read 999 pages. If it has 10,000 pages, you might read 9,999. The work grows linearly with the size of the book. This is O(n).

Approach 2: Open the book to the middle. If the name comes alphabetically before the middle, look left. If after, look right. Repeat. Each step cuts the remaining pages in half. For a 1,000-page book, you need at most 10 steps. For a 10,000-page book, you need at most 14 steps. The work grows logarithmically. This is O(log n).

Approach 3: For every name in the book, check it against every other name for duplicates. That is every name paired with every other name — roughly n times n comparisons. This is O(n^2).

The phone book does not change. The difference is entirely in the approach. Time complexity is how you compare approaches before you commit to one.

3. Syntax / Implementation

Big O notation rules

Before analyzing code, you need to understand the rules Big O follows.

Rule 1: Drop constants

// This loop runs 2n times
for (let i = 0; i < n; i++) { ... }
for (let i = 0; i < n; i++) { ... }
// Time complexity: O(n), not O(2n)
// Constants are dropped because they do not affect growth rate

Rule 2: Drop lower-order terms

// This runs n^2 + n times
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) { ... } // n^2 operations
}
for (let i = 0; i < n; i++) { ... }   // n operations
// Time complexity: O(n^2), not O(n^2 + n)
// The dominant term wins at large n

Rule 3: Different inputs get different variables

// a and b are different arrays
for (let i = 0; i < a.length; i++) { ... }   // O(a)
for (let i = 0; i < b.length; i++) { ... }   // O(b)
// Total: O(a + b), not O(n)
// You cannot combine them into one variable unless they are the same input

Rule 4: Nested loops multiply

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) { ... }
}
// O(n * n) = O(n^2)

The common complexity classes

// O(1) — Constant time
// Runtime does not change regardless of input size
function getFirst(arr) {
  return arr[0]; // one operation, always
}

// O(log n) — Logarithmic time
// Input is halved at each step
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

// O(n) — Linear time
// One operation per element
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n log n) — Linearithmic time
// Typical of efficient sorting algorithms
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

// O(n^2) — Quadratic time
// Nested loop over the same input
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// O(2^n) — Exponential time
// Each call spawns two more calls — recursive without memoization
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

The complexity table

The last row is not a typo. O(2^n) with n of 100 produces a number larger than the number of atoms in the observable universe. No computer runs that.

4. Dry Run

Let us analyze a real piece of code step by step to determine its time complexity.

Problem: Given two arrays, find all elements that appear in both.

function intersection(a, b) {
  const result = [];

  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < b.length; j++) {
      if (a[i] === b[j]) {
        result.push(a[i]);
        break;
      }
    }
  }

  return result;
}

Dry run with a = [1, 2, 3], b = [2, 3, 4]:

i=0, a[0]=1:
  j=0: 1 === 2? No
  j=1: 1 === 3? No
  j=2: 1 === 4? No
  → no match

i=1, a[1]=2:
  j=0: 2 === 2? Yes → push 2, break

i=2, a[2]=3:
  j=0: 3 === 2? No
  j=1: 3 === 3? Yes → push 3, break

Result: [2, 3]

Complexity analysis:

• Outer loop runs a.length times → call it n
• Inner loop runs up to b.length times for each outer iteration → call it m
• In the worst case (no matches), every inner loop runs fully
• Total operations: n * m
• Time complexity: O(n * m)

If both arrays have the same length n, this is O(n^2).

Can we do better?

/**
 * Intersection using hash set
 * Time: O(n + m) | Space: O(n)
 */
function intersection(a, b) {
  const setA = new Set(a); // O(n) to build
  const result = [];

  for (const num of b) { // O(m)
    if (setA.has(num)) { // O(1) lookup
      result.push(num);
    }
  }

  return result;
}

Complexity analysis of the improved version:

• Building setA from array a: O(n)
• Iterating through b: O(m)
• Each has lookup: O(1)
• Total: O(n) + O(m) = O(n + m)

For equal-length arrays, this drops from O(n^2) to O(n). The improvement comes directly from recognizing that hash set lookup is O(1) while array search is O(n).

5. Best Practice Example

Problem: Find the most frequent element in an array.

/**
 * Most Frequent Element
 * Approach: Count frequencies with a hash map, track max as we go
 * Time: O(n) | Space: O(n)
 *
 * We avoid a second pass by updating the best candidate during counting.
 */
function mostFrequent(nums) {
  if (nums.length === 0) return null;

  const frequency = new Map();
  let mostCommon = nums[0];
  let highestCount = 0;

  for (const num of nums) {
    const count = (frequency.get(num) ?? 0) + 1;
    frequency.set(num, count);

    if (count > highestCount) {
      highestCount = count;
      mostCommon = num;
    }
  }

  return mostCommon;
}

console.log(mostFrequent([1, 3, 2, 3, 1, 3])); // 3
console.log(mostFrequent([7]));                  // 7
console.log(mostFrequent([]));                   // null

Why this is good:

• Single pass: frequency counting and max tracking happen together, keeping it O(n)
• No second loop to scan the map for the max — that would still be O(n) overall but adds unnecessary code
• Edge cases handled: empty array returns null
• Variable names communicate exactly what they hold
• Complexity is stated and justified

6. Bad Practice Example

Problem: Same most frequent element problem.

function mf(arr) {
  let res;
  let max = 0;

  for (let i = 0; i < arr.length; i++) {
    let cnt = 0;
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] == arr[j]) cnt++;
    }
    if (cnt > max) {
      max = cnt;
      res = arr[i];
    }
  }

  return res;
}

What is wrong:

1. O(n^2) time complexity: For every element, the inner loop counts its occurrences across the whole array. This is completely avoidable with a hash map.

2. No edge case handling: Empty array returns undefined instead of a deliberate value like null.

3. == instead of ===: Loose equality causes subtle bugs in JavaScript.

4. Variable names mf, res, cnt: None of these communicate meaning. cnt for count is guessable, but res for "the most frequent element" is not self-describing at all.

5. No complexity comment: The author almost certainly does not know this is O(n^2). If they did, they would have used a hash map.

6. Redundant work: The inner loop counts occurrences of arr[i] even for elements already counted in previous iterations. For an array of all identical elements, the same count is computed n times.

This function will pass a small test case. On an input of 100,000 elements, it performs 10 billion comparisons.

7. Time Complexity

Let us go deeper on how to analyze time complexity for different code patterns.

Analyzing loops

// Single loop → O(n)
for (let i = 0; i < n; i++) { ... }

// Loop that halves each iteration → O(log n)
for (let i = n; i > 1; i = Math.floor(i / 2)) { ... }

// Nested loops, both over n → O(n^2)
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) { ... }
}

// Nested loops, inner depends on outer → O(n^2) still
for (let i = 0; i < n; i++) {
  for (let j = i; j < n; j++) { ... }
  // This runs n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 times
  // Still O(n^2)
}

Analyzing recursion

For recursive functions, count the number of calls and the work done per call.

// One recursive call per level, n levels deep → O(n)
function sumDown(n) {
  if (n <= 0) return 0;
  return n + sumDown(n - 1);
}

// Two recursive calls per level, log n levels deep → O(n)
// (binary tree traversal — n total nodes)
function treeSum(node) {
  if (node === null) return 0;
  return node.val + treeSum(node.left) + treeSum(node.right);
}

// Two recursive calls per level, n levels deep → O(2^n)
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

The constraint hint system

Problem constraints directly suggest expected time complexity. Use this as a filter during planning:

n ≤ 20           → O(2^n) or O(n!) — backtracking, permutations
n ≤ 1,000        → O(n^2) — nested loops acceptable
n ≤ 100,000      → O(n log n) — sorting, heap, divide and conquer
n ≤ 1,000,000    → O(n) — linear scan, hash map, two pointers
n ≤ 10^9         → O(log n) or O(1) — binary search or math

If your planned solution does not match what the constraint implies, revise your plan before coding.

8. Space Complexity

Time complexity measures operations. Space complexity measures memory. Both are analyzed using Big O.

For time complexity specifically, space is separate — but the two are often in tension: faster solutions frequently use more memory (like adding a hash map to avoid a nested loop).

This trade-off appears constantly in DSA:

Nested loop (brute force)
  Time: O(n^2)  |  Space: O(1)

Hash map approach
  Time: O(n)    |  Space: O(n)

When an interviewer asks "can you optimize this?", they usually mean time. When they follow up with "can you reduce memory usage?", they are asking you to navigate this trade-off consciously.

Full space complexity analysis is covered in the next tutorial. For time complexity, the key habit is: after analyzing time, always state space as well. They belong together.

9. Common Mistakes

Mistake 1: Forgetting that built-in methods have complexity

// This is NOT O(n) — it is O(n^2)
for (let i = 0; i < arr.length; i++) {
  if (arr.includes(arr[i])) { ... } // includes is O(n)
}

// Common O(n) methods inside loops that create O(n^2):
// arr.includes()   → O(n)
// arr.indexOf()    → O(n)
// arr.splice()     → O(n)
// str.slice()      → O(k) where k is slice length
// arr.unshift()    → O(n) — shifts all elements

How to avoid it: Know the complexity of every built-in method you use. If you are unsure, look it up before assuming O(1).

Mistake 2: Treating O(n + m) as O(n^2)

When two inputs are different, they get different variables. O(n + m) is linear in the total input size, not quadratic. This matters when explaining complexity in an interview — conflating them shows a misunderstanding of the notation.

How to avoid it: If the inputs are different arrays or structures, use separate variables in your analysis.

Mistake 3: Ignoring the dominant term

// This is O(n^2), not O(n^2 + n + 1)
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) { ... } // n^2
}
for (let i = 0; i < n; i++) { ... }   // n
const x = 5;                           // 1

How to avoid it: Always simplify to the dominant term. At large n, n^2 grows so much faster than n that the linear term is irrelevant.

Mistake 4: Assuming recursion is always expensive

Recursion is O(2^n) for naive Fibonacci. But recursion is O(n) for a single linear recursion, and O(log n) for binary search implemented recursively. The cost depends on the structure of the calls, not on the fact that it is recursive.

How to avoid it: Draw the recursion tree. Count the number of nodes (calls). Multiply by the work done at each node.

Mistake 5: Not stating complexity after solving

Many beginners solve a problem, verify the output, and move on. They never ask: what is the complexity? This means they have no idea whether their solution is efficient or how to improve it.

How to avoid it: Make it a rule that a solution is not done until you have stated and verified its time and space complexity. Every time, without exception.

10. Practice Problems

Each of these is chosen to practice complexity analysis, not just problem-solving.

• Easy: "Best Time to Buy and Sell Stock" — solve it in O(n) with a single pass and explain why a nested loop O(n^2) approach is unnecessary. Pattern: single-pass linear scan.

• Easy: "Maximum Subarray" — practice Kadane's algorithm and explain why it is O(n) rather than the obvious O(n^2) brute force. Pattern: dynamic programming / greedy.

• Medium: "Group Anagrams" — analyze whether sorting each string makes this O(n * k log k) and explain what k represents. Pattern: hash map with sorted key.

• Medium: "Top K Frequent Elements" — compare the O(n log n) sort-based approach with the O(n log k) heap-based approach and explain the difference. Pattern: heap / bucket sort.

• Hard: "Median of Two Sorted Arrays" — the target complexity is O(log(m + n)). Understand why a linear merge is not good enough and how binary search achieves logarithmic time. Pattern: binary search on two arrays.

11. Summary

Time complexity is how you measure whether your solution is fast enough to work at scale. It is not a theoretical exercise — it is a practical filter that should be applied to every solution you write.

What to remember:

• Big O describes the growth rate of operations as input grows, not the actual runtime
• Drop constants and lower-order terms: O(2n) is O(n), O(n^2 + n) is O(n^2)
• Different inputs get different variables: O(n + m) is not O(n^2)
• Built-in methods have complexity — calling an O(n) method inside a loop creates O(n^2)
• Use constraint size as a hint: large n means you need O(n) or O(n log n)
• State complexity after every solution, before moving to the next problem

When to use time complexity analysis: before coding (to validate your plan) and after coding (to confirm your solution). Every single time.

Why it matters: A correct solution at O(n^2) fails on large inputs. Interviewers expect you to know the complexity of your solution and be able to discuss whether it can be improved.

Next Topic ->