Introduction to Time and Space Complexity

Table of Contents

Overview Problem Definition Core Principle: Step-by-Step Diagram Detailed Algorithm Steps TypeScript Implementation 1. O(1): Constant time 2. O(log n): Binary search 3. O(n): Linear scan 4. Optimizing O(n²) to O(n)5. Space complexity comparison Engineering Optimization: Look at the Data Size Before Optimizing Applications and Limitations Typical applications Limitations Summary

890 words

4 minutes

Introduction to Time and Space Complexity

2026-04-26

Algorithms

Algorithm Basics

/

Complexity Analysis

/

Big O Notation

Overview#

Time complexity and space complexity are used to describe how the running time and memory usage of code grow as the input size increases. They don’t care about the specific time taken on a particular machine, but rather about the growth trend.

Prerequisites

Input size n: array length, number of nodes, string length, etc.

Loops and recursion: complexity usually comes from the number of repeated executions

Cost of data structure operations: the complexity of APIs for arrays, Maps, Sets, sorting, etc. differs

Problem Definition#

Given a piece of code or an algorithm, estimate its time and space cost as the input size grows.

Element	Description
Input	A program, algorithm, or data structure operation
Output	Time complexity, space complexity, and the main bottleneck
Analysis goal	Find the fastest-growing part, ignoring constants and lower-order terms
Common results	O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)

Core Principle: Step-by-Step Diagram#

Finding one user among 1 million users:

1
interface User {
2
  id: number;
3
  name: string;
4
}
5

6
function findUserLinear(users: User[], id: number): User | null {
7
  for (const user of users) {
8
    if (user.id === id) return user;
9
  }
10
  return null;
11
}
12

13
const userMap = new Map<number, User>();
14
function findUserByMap(id: number): User | undefined {
15
  return userMap.get(id);
16
}

Big O notation keeps only the fastest-growing term:

1
T(n) = 3n² + 100n + 5000  =>  O(n²)
2
T(n) = 50n + 1000         =>  O(n)
3
T(n) = 200                =>  O(1)

Detailed Algorithm Steps#

1
Algorithm: AnalyzeComplexity(code)
2
Input: A piece of code or an algorithm
3
Output: Time complexity and space complexity
4

5
1. Clarify what the input size n represents
6
2. Identify the statements that are repeatedly executed as n grows
7
3. Count the number of loop, recursive, or data structure operations
8
4. Keep the fastest-growing term, ignore constants and lower-order terms
9
5. Count the additionally allocated space; do not count the input itself as additional space

Common complexity comparison:

Complexity	Growth pattern	Typical scenarios
O(1)	Does not change with input size	Array index access, Map lookup
O(log n)	Eliminates half each time	Binary search, heap operations
O(n)	Traverses the input once	Summation, filtering, linear search
O(n log n)	O(n) per level, log n levels total	Merge sort, heap sort
O(n²)	Double enumeration	Brute-force pair matching, matrix traversal
O(2^n)	Each element chosen or not	Subset enumeration, naive recursion

TypeScript Implementation#

1. O(1): Constant time#

1
function getFirst<T>(arr: T[]): T | undefined {
2
  return arr[0];
3
}
4

5
function getByKey<K, V>(map: Map<K, V>, key: K): V | undefined {
6
  return map.get(key);
7
}

2. O(log n): Binary search#

1
function binarySearch(nums: number[], target: number): number {
2
  let left = 0;
3
  let right = nums.length - 1;
4

5
  while (left <= right) {
6
    const mid = left + Math.floor((right - left) / 2);
7
    if (nums[mid] === target) return mid;
8
    if (nums[mid] < target) left = mid + 1;
9
    else right = mid - 1;
10
  }
11

12
  return -1;
13
}

3. O(n): Linear scan#

1
function sum(nums: number[]): number {
2
  let total = 0;
3
  for (const num of nums) {
4
    total += num;
5
  }
6
  return total;
7
}
8

9
function findMax(nums: number[]): number {
10
  let max = nums[0];
11
  for (const num of nums) {
12
    if (num > max) max = num;
13
  }
14
  return max;
15
}

4. Optimizing O(n²) to O(n)#

1
function findDuplicatesSlow(nums: number[]): number[] {
2
  const result: number[] = [];
3

4
  for (let i = 0; i < nums.length; i++) {
5
    for (let j = i + 1; j < nums.length; j++) {
6
      if (nums[i] === nums[j]) result.push(nums[i]);
7
    }
8
  }
9

10
  return result;
11
}
12

13
function findDuplicatesFast(nums: number[]): number[] {
14
  const seen = new Set<number>();
15
  const duplicates = new Set<number>();
16

17
  for (const num of nums) {
18
    if (seen.has(num)) duplicates.add(num);
19
    else seen.add(num);
20
  }
21

22
  return [...duplicates];
23
}

5. Space complexity comparison#

1
function reverseInPlace<T>(arr: T[]): T[] {
2
  let left = 0;
3
  let right = arr.length - 1;
4

5
  while (left < right) {
6
    [arr[left], arr[right]] = [arr[right], arr[left]];
7
    left++;
8
    right--;
9
  }
10

11
  return arr;
12
}
13

14
function reverseNew<T>(arr: T[]): T[] {
15
  const result: T[] = [];
16
  for (let i = arr.length - 1; i >= 0; i--) {
17
    result.push(arr[i]);
18
  }
19
  return result;
20
}

Engineering Optimization: Look at the Data Size Before Optimizing#

The purpose of complexity analysis is not to make all code extremely optimized, but to determine where the risk lies at the current data scale.

Data size	Rule of thumb	Recommendation
< 1,000	Most approaches are acceptable	Prioritize readability
1,000 ~ 100,000	Avoid O(n²)	Use Map/Set, sorting, two pointers
100,000 ~ 1,000,000	Watch out for large constants and memory copying	Prefer O(n log n) or O(n)
> 1,000,000	Focus on indexing, pagination, streaming	Aim for O(log n) / O(1) queries

Frontend scenarios also have complexity issues: rendering large lists, search suggestions, table filtering, and component tree re-rendering all require attention to input size.

Applications and Limitations#

Typical applications#

Assessing whether an algorithm solution can pass within the data range
Determining the performance risk of APIs, lists, and searches under large data volumes
Choosing data structures such as arrays, Maps, Sets, heaps, and trees
Explaining the cost of sorting, searching, traversal, and recursion

Limitations#

Limitation	Description
Ignores constants	O(n) is not always faster than O(n log n)
Ignores hardware factors	Cache, IO, and network latency may matter more
Average and worst case differ	Hashing, quicksort, etc. need to distinguish scenarios
Only looks at growth trends	With small data, readability is often more important than complexity

Summary#

Key points:

Big O describes the growth trend, not the exact running time.
Time complexity looks at the number of executions; space complexity looks at extra usage.
Map/Set are often used to trade space for time, reducing O(n²) to O(n).
Before optimizing, look at the data size first, to avoid sacrificing readability for small-scale scenarios.