# Proving lower bounds

Show that it is impossible to have any other algorithm (for a common problem) whose time complexity is less than L(n) for random input.

## More examples

Consider the Tower of Hanoi^{ᛦ} problem.

Show that it is impossible to have any other algorithm (for a common problem) whose time complexity is less than L(n) for random input.

Consider the Tower of Hanoi^{ᛦ} problem.