big-o - 需要帮助弄清楚这个说法是否正确

Question

我的任务是弄清楚这个说法是否正确

左边的表达式是否等于n^3的big theta？

根据我的理解，如果我们谈论的是大 O，那将是正确的，因为 n^3 是增长最快的项，但我不确定大 theta。

Answer 1

让

f(n) = 1/4 n^3 + n^2 log(n) + 17 n^2

然后

f(n)/n^3 = 1/4 + log(n)/n + 17/n

所以

lim f(n)/n^3 = 1/4 + 0 + 0 = 1/4

意思是-ε < f(n)/n^3 - 1/4 < ε对于 n > n0 .取ε = 1/8 .然后

1/4 - 1/8 < f(n)/n^3 < 1/8 + 1/4
1/8 < f(n)/n^3 < 3/8
n^3 < 8f(n) < 3n^3

服用 ϴ()

ϴ(n^3) <= ϴ(f(n)) <= ϴ(n^3)

因为ϴ将所有乘法因子视为 1 .