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.