Prove that the running time of an algorithm is if and only if its worst-case running time is and its best-case running time is .

Let’s assume that the running time of the algorithm is . If , then for .

As for , , i.e. is upper bounded by . In other words, worst-case running time of the algorithm is .

And as for , , i.e. is lower bounded by . In other words, best-case running time of the algorithm is .

Similarly we can prove the reverse as we did in Exercise 3.1-5.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.