Case 1: $O(N\log{N})$ and $O(N^2)$

Quicksort

1
2
3
4
5
quicksort(num, lo, hi) {
p = partition(num, lo, hi) // O(hi - lo)
quicksort(num, lo, p);
quicksort(num, p + 1, hi);
}

The complexity is dependent on whether the partition halves the data.

  • Time:
    • Best: $T(N) = 2T(N/2) + O(N) = O(N\log{N})$
    • Worst: $T(N) = T(N - 1) + T(1) + O(N) = O(N^2)$
    • Non-worst: $T(N) = T(N/10) + T(9N/10) + O(N) = O(N\log{N})$
  • Space:
    • Best: $O(\log{N})$
    • Worst: $O(N)$

Mergesort

1
2
3
4
5
6
mergesort(num, lo, hi) {
mid = lo + (hi - lo) / 2;
mergesort(num, lo, mid);
mergesort(num, mid + 1, hi)
merge(num, lo, mid, hi) // O(hi - lo)
}
  • Time:
    • Best: $T(N) = 2T(N/2) + O(N) = O(N\log{N})$
    • Worst: $O(N\log{N})$ since the partition always halves the array.
  • Space:
    • $O(N) = O(\log{N} + N)$ since mergesort needs an auxiliary array.

Case 2: $O(\log{N})$ and $O(N)$

1
2
3
4
5
6
7
8
9
10
binarySearch(num, lo, hi) {
mid = lo + (hi - lo) / 2;
if (some condition) {
binarySearch(num, lo, mid);
} else if (some condition) {
binarySearch(num, mid + 1, hi);
} else {
return num[mid];
}
}
  • Time: $T(N) = T(N/2) + O(1) = O(\log{N})$
  • Space: $O(\log{N})$

Binary Tree Traversal

1
2
3
4
5
inorder(root) {
inorder(root.left);
print(root.val); // visit - O(1)
inorder(root.right);
}
  • Time:
    • Best: $T(N) = 2T(N/2) + O(1) = O(N)$ if the tree is perfect or bushy.
    • Worst: $T(N) = T(N - 1) + T(1) + O(1) = O(N)$ if the tree is spindly.
    • Note: Notice that the runtimes are the same.
  • Space:
    • Best: $O(\log{N})$ if the tree is perfect or bushy.
    • Worst: $O(N)$ if the tree is spindly.
  • Variant:
    • If the visiting part takes more than $O(1)$, say $O(N)$, the runtime would be similar to Quicksort, which depends on the partition. And $O(N)$ is the total amount of work at each level (please imagine the situation in a binary tree).

Case 3: $O(2^N)$ and $O(N!)$

Combination

  • $N$ is the total job size
  • Initially, call: combination(0, 0)
  • For each depth, call combination() for $N$ times.
1
2
3
4
5
6
7
8
combination(depth, start) {
if (depth == N) {
return ...
}
for (int i = start; i < N; ++i) { // the work size keep decreasing
combination(depth + 1, i);
}
}
  • Time: $T(N) = T(N - 1) + T(N - 2) + \ldots + T(1) = O(2^N)$
  • Space: $O(N)$

Permutation

1
2
3
4
5
6
7
8
9
10
11
permutation(depth, used) {
if (depth == N) {
return ...
}
for (int i : 0...N) { // the workload does not change
if (i in used) continue;
used.add(i);
permutation(depth + 1, used);
used.remove(i);
}
}
  • Time: $T(N) = N * T(N -1) = O(N!)$
  • Space: $O(N)$

Case 4: DP

Fibonacci

1
2
3
4
fib(n) {
if (n < 1) return 1;
return fib(n - 1) + fib(n - 2);
}
  • Time: $T(N) = T(N - 1) + T(N - 2) + O(1) = O(2^N) = O(1.618^N)$
  • Space: $O(N)$

Fibonacci with DP

1
2
3
4
5
6
fib(n) {
if (n < 1) return 1;
if (m[n] > 0) return m[n];
m[n] = fib(n - 1) + fib(n - 2);
return m[n];
}
  • Time:
    • Number of subproblems $N$ $\times$ Exclusive time to solve each subproblem $O(1)$
    • $T(N) = O(N)$
  • Space:
    • Max depth of call stack $\times$ Space used by each subproblem
    • $O(N)$

More to go when you work on DP problems


Comment