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 problem.