函数运行时间的精确Θ表示法

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

如果你继续使用西格玛符号，得到T(n)等于某物，那么你就得到了大Theta。

如果T(n)小于或等于，那么它就是大O。

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

​

​