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 (inti= start; i < N; ++i) { // the work size keep decreasing combination(depth + 1, i); } }

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); } }