Analysis of shell sort

I am reading a book on algorithms it is mentioned on analysis of shell sort algorithm as below:

The worst-case running t开发者_开发技巧ime 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:

1. 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!

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.