Runtime Overview

When learning about algorithms and data structures, you'll frequently encounter the term "time complexity". This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size.

What is Time Complexity?

Time complexity represents the amount of time an algorithm takes to run as a function of the length of the input. It provides an upper bound on the running time, helping us understand the worst-case scenario in terms of performance.

Why is Time Complexity Important?

Imagine you have two solutions to sort a list of numbers. While both give the correct answer, one takes a minute for a list of 1000 numbers, and the other takes only a second. Naturally, you'd choose the faster one. Time complexity helps us predict these differences without having to run the algorithms with actual large inputs.

The important thing about runtime complexity is that we usually do not consider constants when analyzing the time complexity. We usually want to find the "family" of functions that most closely match the growth in computational time. For instance, O(2n) and O(5n) can be loosely said to belong to the family of functions O(n).

This is the standard notation to describe an algorithm's time complexity. When we say an algorithm has a time complexity of O(n), we mean that in the worst case, the algorithm's running time grows linearly with the input size.

Imagine we had a program that printed all the integers from 1 to n with a single for loop. The time complexity of the program would be O(n). Even if the program printed all the integers from -100 to 5 * n, the time complexity wouldn't change because the running time still grows linearly with n.

One may want to consider optimizing algorithms to have a better constant in some specific cases. In most cases, however, this is unnecessary, and basic runtime analysis can indicate how efficient a solution is.

As a general rule of thumb, coding challenges platforms typically allow your solutions to have a maximum of 10-20 million operations. Using this information, we can deduce it from the constraints in the problem description. Here's a short video explaining how to do this:

Here's a more granular breakdown of the most common time complexities, their corresponding maximum input size, and common algorithms required to achieve them:

`O(1)`

Constant time complexity. Could be

Hashmap lookup
Array access and update
Pushing and popping elements from a stack
Finding and applying math formula
Typically for n > 10⁹

The following code is O(1) because it executes a constant number of operations:

1a = 5
2b = 7
3c = 4
4d = a + b + c + 153
5

1int a = 5;
2int b = 7;
3int c = 4;
4int d = a + b + c + 153;
5

1int a = 5;
2int b = 7;
3int c = 4;
4int d = a + b + c + 153;
5

1var a = 5;
2var b = 7;
3var c = 4;
4var d = a + b + c + 153;
5

`O(log(N))`

log(N) grows VERY slowly. log(1,000,000) is only about 20. In fact, lookup by primary key in a relational database is log(N) (many mainstream relational databases such as postgres use B-trees for indexing by default, and searching in a B-tree is log(N)).

In coding interviews, log(N) typically means

Binary search or variant
Balanced binary search tree lookup
Processing the digits of a number
Typically for n > 10⁸

Note: Unless specified, we assume that log(N) refers to log₂(N) or "log base 2 of N"

The following code is O(log(N)) because N is halved each iteration, so the amount of work is logarithmic:

1N = 100000000
2while N > 0:
3  # some constant operation
4  N //= 2
5

1int N = 100000000;
2while (N > 0) {
3  // some constant operation
4  N /= 2;
5}
6

1int N = 100000000;
2while (N > 0) {
3  // some constant operation
4  N /= 2;
5}
6

1var N = 100000000;
2while (N > 0) {
3  // some constant operation
4  N /= 2;
5}
6

`O(N)`

Linear time typically means looping through a linear data structure a constant number of times. Most commonly, this means

Going through array/linked list
Two pointers
Some types of greedy
Tree/graph traversal
Stack/Queue
Typically for n ≤ 10⁶

The following examples are both O(N):

1for i in range(1, N + 1):
2  # constant time code
3
4i = 0
5while i < N:
6  # constant time code
7  i += 1
8

1for (int i = 1; i <= N; i++) {
2  // constant time code
3}
4
5int i = 0;
6while (i < N) {
7  // constant time code
8  i++;
9}
10

1for (int i = 1; i <= N; i++) {
2  // constant time code
3}
4
5int i = 0;
6while (i < N) {
7  // constant time code
8  i++;
9}
10

1for (let i = 1; i <= N; i++) {
2  // constant time code
3}
4
5var i = 0;
6while (i < N) {
7  // constant time code
8  i++;
9}
10

Because we also ignore constant factors and lower order terms, the following are also O(N):

1for i in range(1, 5 * N + 17):
2  # constant time code
3
4for i in range(1, N + 538238):
5  # constant time code
6

1for (int i = 1; i < 5 * N + 17; i++) {
2  // constant time code
3}
4
5for (int i = 1; i < N + 538238; i++) {
6  // constant time code
7}
8

1for (int i = 1; i < 5 * N + 17; i++) {
2  // constant time code
3}
4
5for (int i = 1; i < N + 538238; i++) {
6  // constant time code
7}
8

1for (let i = 1; i < 5 * N + 17; i++) {
2  // constant time code
3}
4
5for (let i = 1; i < N + 538238; i++) {
6  // constant time code
7}
8

`O(K log(N))`

Heap push/pop K times. When you encounter problems that seek the "top K elements", you can often solve them by pushing and popping to a heap K times, resulting in an O(K log(N)) runtime. e.g., K closest points, merge K sorted lists.
Binary search K times.
Typically for n ≤ 10⁶

We will discuss more about this in the heap section.

`O(N log(N))`

Sorting. The default sorting algorithm's expected runtime in all mainstream languages is N log(N). For example, java uses a variant of merge sort for object sorting and a variant of Quick Sort for primitive type sorting.
Divide and conquer with a linear time merge operation. Divide is normally log(N), and if merge is O(N) then the overall runtime is O(N log(N)). An example problem is smaller numbers to the right.
Typically for n ≤ 10⁶

1N = int(input())
2ar = []
3for i in range(N):
4  m = int(input())
5  ar.append(m)
6ar.sort() # nlogn
7

1int N = sc.nextInt();
2ArrayList<Integer> ar = new ArrayList<>();
3for (int i = 0; i < N; i++) {
4  int m = sc.nextInt();
5  ar.add(m);
6}
7Collections.sort(ar); // nlogn
8

1int N;
2cin >> N;
3vector<int> ar;
4for (int i = 0; i < N; i++) {
5  int m;
6  cin >> m;
7  ar.emplace_back(m);
8}
9sort(ar.begin(), ar.end()) // nlogn
10

1var N = parseInt(gets());
2let ar = [];
3for (let i = 0; i < N; i++) {
4  var m = parseInt(gets());
5  ar.push(m);
6}
7ar.sort(); // nlogn
8

`O(N^2)`

Also called quadratic time.

Nested loops, e.g., visiting each matrix entry
Many brute force solutions
Typically for n ≤ 3000

For small N < 1000, this is not that bad for modern computers. You can probably pass most Leetcode tests with quadratic time for tiny Ns. However, in an interview, your solution usually has to do better than quadratic time to impress the interviewer if there is a better solution.

This example is O(N^2) because the outer loop runs O(N) iterations and the inner loop O(N) as well:

1for i in range(1, N + 1):
2  for j in range(1, N + 1):
3    # constant time code
4

1for (int i = 1; i <= N; i++) {
2  for (int j = 1; j <= N; j++) {
3    // constant time code
4  }
5}
6

1for (int i = 1; i <= N; i++) {
2  for (int j = 1; j <= N; j++) {
3    // constant time code
4  }
5}
6

1for (let i = 1; i <= N; i++) {
2  for (let j = 1; j <= N; j++) {
3    // constant time code
4  }
5}
6

For this example, the outer loop runs O(N) iterations, and the inner loop runs anywhere between 1 and N iterations. Since Big O notation calculates worst-case time complexity, we treat the inner loop as a factor of N. Thus, this code is O(N^2).

1for a in range(1, N + 1):
2  for j in range(a, N + 1):
3    # constant time code
4

1for (int a = 1; a <= N; a++) {
2  for (int j = a; j <= N; j++) {
3    // constant time code
4  }
5}
6

1for (int a = 1; a <= N; a++) {
2  for (int j = a; j <= N; j++) {
3    // constant time code
4  }
5}
6

1for (let a = 1; a <= N; a++) {
2  for (let j = a; j <= N; j++) {
3    // constant time code
4  }
5}
6

`O(2^N)`

Grows very rapidly. Often requires memoization to avoid repeated computations and reduce complexity.

Combinatorial problems, backtracking, e.g. subsets
Often involves recursion and is harder to analyze time complexity at first sight
Further detailed code examples can be found in the backtracking section
Typically for n ≤ 20

A recursive Fibonacci algorithm is O(2^N) because for any Fib(i) where i > 1, we call Fib(i - 1) and Fib(i - 2).

1def Fib(n):
2  if n == 0 or n == 1:
3    return 1
4  return Fib(n - 1) + Fib(n - 2)
5

1public static int Fib(int n) {
2  if (n == 0 || n == 1) {
3    return 1;
4  }
5  return Fib(n - 1) + Fib(n - 2);
6}
7

1int Fib(int n) {
2  if (n == 0 || n == 1) {
3    return 1;
4  }
5  return Fib(n - 1) + Fib(n - 2);
6}
7

1function Fib(n) {
2  if (n === 0 || n === 1) {
3    return 1;
4  }
5  return Fib(n - 1) + Fib(n - 2);
6}
7

`O(N!)`

Grows insanely rapidly. Only solvable by computers for small N. Often requires memoization to avoid repeated computations and reduce complexity.

Combinatorial problems, backtracking, e.g. permutations
Often involves recursion and is harder to analyze time complexity at first sight
Detailed code examples can be found in the backtracking section
Typically for n ≤ 12

Amortized Time Complexity

The idea of amortized time is doing a very costly task once in a while. The costly task is done so rarely that it is dilluted away. For example, if we had N O(1) tasks but only a single O(N) task, we could still consider the total O(N) instead of O(N^2) if N is large enough.

The key takeaway is that amortized time is the average time taken per operation.

The following is an implementation of an O(1) append function for a dynamically sized array:

1size = None # number of elements in array
2capacity = None # maximum number of elements array can store
3arr = []
4...
5def append(x):
6  if size == capacity:
7    new_arr = [None] * (2 * capacity)
8    capacity *= 2
9    for i in range(size):
10      new_arr[i] = arr[i]
11    arr = new_arr
12  arr[size] = x
13  size += 1
14

1int size; // number of elements in array
2int capacity; // maximum number of elements array can store
3int[] arr;
4...
5public static void append(int x) {
6  if (size == capacity) {
7    int[] newArr = new int[2 * capacity];
8    capacity = capacity * 2
9    for (int i = 0; i < size; i++) {
10      newArr[i] = arr[i];
11    }
12    arr = newArr;
13  }
14  arr[size] = x;
15  size++;
16}
17

1int size; // number of elements in array
2int capacity; // maximum number of elements array can store
3int arr[] = {};
4...
5void append(int x) {
6  if (size == capacity) {
7    int new_arr[2 * capacity];
8    capacity = capacity * 2;
9    for (int i = 0; i < size; i++) {
10      new_arr[i] = arr[i];
11    }
12    arr = new_arr;
13  }
14  arr[size] = x;
15  size++;
16}
17

1var size; // number of elements in array
2var capacity; // maximum number of elements array can store
3const arr = [];
4...
5function append(x) {
6  if (size === capacity) {
7    const newArr = new Array(2 * capacity);
8    capacity = capacity * 2;
9    for (let i = 0; i < size; i++) {
10      newArr[i] = arr[i]
11    }
12    arr = newArr;
13  }
14  arr[size] = x;
15  size++;
16}
17

Big O Notation Practice

Answers for these questions will be at the end of this article.

What is the asymptotic time bound of functions with these time complexities?

3N + 2N + N
2N^3 + 5N^2
N + log(N)
N^2log(N)
2^N + N^2
10

What is the time complexity of this code?

1N = int(input())
2ar = [0] * N
3for i in range(N):
4  ar[i] = int(input())
5max_val = ar[0]
6for i in range(1, N):
7  max_val = max(max_val, ar[i])
8print(max_val)
9

1int N = sc.nextInt();
2int[] ar = new int[N];
3for (int i = 0; i < N; i++) {
4  ar[i] = sc.nextInt();
5}
6let maxVal = ar[0];
7for (int i = 1; i < N; i++) {
8  maxVal = Math.max(maxVal, ar[i]);
9}
10System.out.println(maxVal);
11

1int N;
2cin >> N;
3int ar[N];
4for (int i = 0; i < N; i++) {
5  cin >> ar[i];
6}
7int max_val = ar[0];
8for (int i = 1; i < N; i++) {
9  max_val = max(max_val, ar[i]);
10}
11cout << max_val << endl;
12

1var N = parseInt(gets());
2const ar = new Array(N);
3for (let i = 0; i < N; i++) {
4  ar[i] = parseInt(gets());
5}
6let maxVal = ar[0];
7for (let i = 1; i < N; i++) {
8  maxVal = Math.max(maxVal, ar[i]);
9}
10console.log(maxVal);
11

What is the time complexity of this code?

1N = int(input())
2ar = [[0] * N for _ in range(N)]
3for i in range(N):
4  for j in range(N):
5    ar[i][j] = int(input())
6
7for i in range(N):
8  ar[i].sort()
9

1int N = sc.nextInt();
2int[][] ar = new int[N][N];
3for (int i = 0; i < N; i++) {
4  for (int j = 0; j < N; j++) {
5    ar[i][j] = sc.nextInt();
6  }
7}
8for (int i = 0; i < N; i++) {
9  Arrays.sort(ar[i]);
10}
11

1int N;
2cin >> N;
3int ar[N][N];
4for (int i = 0; i < N; i++) {
5  for (int j = 0; j < N; j++) {
6    cin >> ar[i][j];
7  }
8}
9for (int i = 0; i < N; i++) {
10  sort(ar[i], ar[i] + N);
11}
12

1var N = parseInt(gets());
2const ar = new Array(N).fill(new Array(N));
3for (let i = 0; i < N; i++) {
4  for (let j = 0; j < N; j++) {
5    ar[i][j] = parseInt(gets());
6  }
7}
8for (let i = 0; i < N; i++) {
9  ar[i].sort();
10}
11

What is the time complexity of this code?

1# assume an O(1) swap(a, b) function that swaps the values a and b
2N = int(input())
3ar = [[0] * N] * N
4for i in range(N):
5  for j in range(N/2):
6    swap(ar[i][j], ar[i][N - j])
7

1// assume an O(1) swap(a, b) function that swaps the values a and b
2int N = sc.nextInt();
3int[][] ar = new int[N][N];
4for (int i = 0; i < N; i++) {
5  for (int j = 0; j < N / 2; j++) {
6    swap(ar[i][j], ar[i][N - j]);
7  }
8}
9

1// assume an O(1) swap(a, b) function that swaps the values a and b
2int N;
3cin >> N;
4int ar[N][N];
5for (int i = 0; i < N; i++) {
6  for (int j = 0; j < N / 2; j++) {
7    swap(ar[i][j], ar[i][N - j]);
8  }
9}
10

1// assume an O(1) swap(a, b) function that swaps the values a and b
2var N = parseInt(gets());
3const ar = new Array(N).fill(new Array(N));
4for (let i = 0; i < N; i++) {
5  for (let j = 0; j < N / 2; j++) {
6    swap(ar[i][j], ar[i][N - j]);
7  }
8}
9

What is the time complexity of this code?

1# assume the log2(N) function takes O(1) time
2# assume string concatenation takes O(1) time
3def func(str, idx, len):
4  if idx == len:
5    # ...  an O(1) op
6  else:
7    func(str + "a", idx + 1, len)
8    func(str + "b", idx + 1, len)
9...
10N = int(input())
11func("", 0, int(log2(N)))
12

1// assume the log2(N) function takes O(1) time
2// assume string concatenation takes O(1) time
3public static void func(String str, int idx, int len) {
4  if (idx == len) {
5    // ...  an O(1) op
6  } else {
7    func(str + "a", idx + 1, len);
8    func(str + "b", idx + 1, len);
9  }
10}
11...
12int N = sc.nextInt();
13func("", 0, (int)log2(N));
14

1// assume the log2(N) function takes O(1) time
2// assume string concatenation takes O(1) time
3void func(string str, int idx, int len) {
4  if (idx == len) {
5    // ...  an O(1) op
6  } else {
7    func(str + "a", idx + 1, len);
8    func(str + "b", idx + 1, len);
9  }
10}
11...
12int N;
13cin >> N;
14func("", 0, (int)log2(N));
15

1// assume the log2(N) function takes O(1) time
2// assume string concatenation takes O(1) time
3function func(str, idx, len) {
4  if (idx === len) {
5    // ...  an O(1) op
</