math - 如何计算 Big O 的见证对？

Question

有人可以解释在必须证明 log n^2 是 O(log n) 的情况下如何使用见证对吗？请举例说明您是如何提出任何特定证人对的。

Answer 1

根据对数的幂律，我们有

日志 (n ² ) = 2 日志 n

因此，对于 n 的任意选择，log (n ² ) = 2 log n。因此，如果我们选择 n ₀ = 1 和 c = 2，对于任何 n ≥ n ₀ ，我们有log (n ² ) ≤ c log n。

希望这可以帮助！