log n

$${{n - 1} \over 2}$$

$${n \over 2}$$

$${{n + 1} \over 2}$$

Optimal binary search tree construction can be performed efficiently using dynamic programming.

Breadth-first search cannot be used to find connected components of a graph

Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.

Depth-first search can be used to find connected components of a graph.

Heapsort

Quicksort

Merge sort

Radix sort