作为函数的精确Θ符号作为运行时间的约束

Question

我正在读考试，我遇到了以下问题：

为以下函数提供运行时间的精确（Θ符号）界限，作为n的函数

for i = 1 to n {
    j = i
    while j < n {
        j = j + 4
    }
}

我相信答案是O（n ^ 2），虽然我肯定是主题的业余但是m推理是初始循环需要O（n）而内循环需要O（n / 4）导致O（ N ^ 2/4）。当O（n ^ 2）占主导地位时，它简化为O（n ^ 2）。

任何澄清将不胜感激。

Answer 1

如果你继续使用Sigma表示法，并获得T（n）等于某事，那么你就得到了Big Theta。

如果T（n）小于或等于，那么它就是大O.

如果T（n）大于或等于，那么它就是大欧米茄。