algorithm - shell排序分析

Question

我正在看一本关于算法的书，它在shell排序算法分析中提到如下:

Shellsort 的最坏情况运行时间，使用 Shell 的增量，是 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.

我的问题是:

1. 为什么作者提到要检查下限的坏情况？我教过我们应该采取最好的情况下限，请要求澄清以上内容。

谢谢!

Answer 1

他同时考虑上限和下限的原因是因为他想使用Theta(Θ) 表示法 来表达最坏情况下的时间。

The theta notation requires you to establish both a upper bound and a lower bound.