How can we prove that the running time bound of an algorithm is tight?

Question

Suppose we can prove that an algorithm, invoked with an input of size n, runs in time O(f(n)).

I want to prove that this running time bound is tight. Two questions:

1. Wouldn't it suffice to give a special input and show that the running time is at least f(n)?
2. I've read that one possibility for proving the tightness is to "reduce sorting to it". I've no idea what is meant by that

Answer 1

Wouldn't it suffice to give a special input and show that the running time is at least f(n)?

Yes, assuming you are talking about the worst case complexity.
If you are talking about worst case complexity - and you have proved it is running in O(f(n)), if you find an input that "worse" than C*f(n)) for some constant C - you effectively proved that the algorithm (under worst case performance) is in Ω(f(n)), and since O(f(n)) [intersection] Ω(f(n)) = Theta(f(n)), it means your algorithm is running in Theta(f(n)) under worst case analysis.
Note that it should actually be a "family" of examples, since if I claim "yes, but this is correct only for small n values, and not for n>N (for some N), you can show me that this family of examples also covers the case where n>N, and still be valid.

Symmetrically, if you proved an algorithm has best case performance of Ω(f(n)), and you found some input that runs "better" (faster) than C*f(n)) for some constant C, you effectively proved the algorithm is Theta(f(n)) under best case analysis.

This trick does NOT work for average case analysis - where you should calculate the expectancy of the run time, and a singular example is not helpful.

I've read that one possibility for proving the tightness is to "reduce sorting to it". I've no idea what is meant by that

This is done to prove a much stronger claim, that there is no algorithm (at all) that can solve some problem at the desired time.
The common usage of it is to assume there is some black box algorithm A that runs in some o(g(n)) time, and then use A to build a sorting algorithm that runs in o(nlogn) time. However, since sorting is Ω(nlogn) problem, we have a contradiction, and we can conclude out assumptions about A are wrong, and it cannot run in the desired time.

This helps us to prove a stronger claim: Not only OUR algorithm has this lower bound, but ALL algorithms that solve the specific problem has this lower bound.