I am reading a book on algorithms it is mentioned on analysis of shell sort algorithm as below:
The worst-case running time of Shellsort, using Shell's increments, is Theta(n square).
The proof requires showing not only an upper bound on the worst-case running time but also showing that there exists some input that actually takes lower bound as Omeaga(n square) time to run. We prove the lower bound first, by constructing a bad case.
My question on above is:
- why author is mentioning bad case to check for lower bound? I taught to get lower bound we should take best case, Kindly request to clarify above.
Thanks!
3 Answers
The reason he is considering both upper bound and lower bound is because he wants to express worst-case time using Theta(Θ) notation.
The theta notation requires you to establish both a upper bound and a lower bound.
Theta is a bounding constraint (both upper and lower). To show an algorithm has running time Theta(f(n)) you have to establish two things:
1) in the worst case, the algorithm runs in time O(f(n)) for all cases [worst case complexity]
2) The lgorithm must take time Omega(f(n)) [there are real examples that hit the worst case scenario]
You establish the second part by finding particularly bad cases for the algorithm.
To show that something is Theta(f(n)), one has to show both an upper and a lower bound, which is what the text is doing.
The claim that "the worst-case time is Theta(n square)" requires one to demonstrate both an upper and a lower bound for said worst-case time.
Similarly, a statement about the average-case time being Theta(f(n)) would require two bounds on the average-case time.
And so on.
As @Patrick87 succinctly puts it:
the bound is orthogonal to the case.
