为给定的运行时函数 f(n)=O(n^2)+nlog(n) 寻找可能的大 theta？

Question

假设 f( n ) = O( n ² ) +  n  log  n。以下哪些是可能的？

1. f( n ) = ?(log n )
2. f( n ) = ?( n )
3. f( n ) = ?( n ² )
4. f( n ) = ?( n ³ )

由于包含 O( n ² ) ，我对运行时函数有点困惑。我相信答案是 2 和 3，因为它们中的每一个都可以乘以一个数字以达到 O( n ² )。具体地，可以将?( n ² )乘以1达到上限O( n ² )，并且可以将?( n )乘以n达到上限O( n ² )。

我对么？

Answer 1

我想唯一正确的答案是（3）。O(n^2)是任何增长一样快n^2或减慢的函数。n log n = O(n^2)，O(n^2) + n log n渐近“介于”n log n和的任何函数也是如此n^2。在您问题中的所有 Thetas 中，只有第三个符合这些界限。