big-o - 为函数提供 Big O、Big Theta 和 Big Omega

Question

一个人怎么能给大 O、大 Theta 或大欧米茄这样的功能

T(n) = n + 10*log n

有人可以告诉我如何获得这种事情的复杂性吗？

Answer 1

去掉所有低阶项和常数，你会得到：

Θ(T(n)) = Θ(n + 10*log(n)) = Θ(n)

由于这是一个紧界 ( Θ)，我们还将上限和下界推断为O(n)和Ω(n)。