※ 引述《mqazz1 (無法顯示)》之銘言：
: Given the definition Θ[theta] is as follows: f(n) = Θ(g(n))
: if and only if there exist positive constants c1, c2 and n0
: such that c1*g(n) <= f(n) <= c2*g(n) for all n, n >= n0.
: Show that the following equalities are incorrect.
: (1) n^2 / logn = Θ(n^2)
假設c1和n0存在，使得c1 * (n^2) <= n^2 / log n對於所有n >= n0成立。
也就是c1 <= 1/log n對於所有 n >= n0成立
但是當n >= 10^(1/c1)的時候，c1 >= 1/log n，所以必定無法滿足條件。
: (2) n^k + ε + (n^k)logn = Θ(n^k + ε)
假設c2和n0存在，使得n^k + ε + (n^k)logn <= c2 * (n^k + ε)
對於所有n >= n0成立。
也就是log n <= (c2-1)(1+ε/n^k)
但是當 n >= 10^(c2-1)(1+ε) 的時候，log n >= (c2-1)(1+ε/n^k)，
所以必定無法滿足條件。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50