証明が解けなくて困っています。ここで、t(n) <= c(5n + 9nlogn^5)、c は定数です。一般に、Big Omega は Big O の反対であり、最良のシナリオであり、下限を探します。したがって、n >= n0 となる ac と n0 が存在します。しかし、これを証明に適用する方法と、方程式の定数を操作して c と n0 を見つけ、t(n) が であることを証明する方法がわかりませんOmega(5n + 9nlogn^5)。
t(n) = n + n logn^2 is/= Omega(5n + 9nlogn^5)
この種の問題を解決する方法について、誰かが洞察を提供できますか?
Big-Omegaの定義によれば、f(n) is Ω( g(n) )数学的
0 ≤ C⋅g(n) ≤ f(n)には、任意の定数C > 0とn > n'
Here、
f(n) = n + n⋅log(n²) = n + 2⋅n⋅log(n)およびを意味し
g(n) = 5n + 9n⋅log(n⁵) = 5n + 45n⋅log(n)ます。
そして私たちは証明したい0 ≤ C * g(n) ≤ f(n)。
さてC = 1/45、
(1/45)⋅(5n + 45n*log(n)) = (n/9 + n⋅logn) <= (n + 2n⋅logn)
したがって、0 ≤ (1/45)⋅g(n) ≤ f(n)⇒ f(n) is Ω(g(n)) for C = 1/45 and n > 0。