运行 快排时间

Question

假设 B(n) 和 W(n) 分别是使用 Quick Sort 对大小为 n 的数组进行排序的最佳情况和最坏情况渐近 运行 次。考虑以下两个语句：

(1): B(n) is O(W(n))
(2): B(n) is Theta(W(n))

Select 一个答案：

A. Both (1) and (2) are true
B. (1) is true but (2) is false
C. (1) is false but (2) is true
D. Both (1) and (2) are false

我认为答案是 A 但我不确定

Answer 1

B(n) = O(n * lg(n))

W(n) = O(n^2)

1) B(n) < W(n) 意味着 B(n) = O(W(n))。

2) B(n) = Theta(W(n)) 等于 W(n) = O(B(n))。与之前 B(n) < W(n) 一样，因此 W(n) 不受 B(n) 的限制，使得第二个陈述不正确。

答案是B，第一个陈述是正确的，第二个是错误的。