nlog (n) Big Theta (n)입니까? 마스터 정리

Question

Θ (n)의 nlog (n)입니까?
Im은 master theorem을 사용하여 reccurrences를 해결하기 때문에 이것을 묻습니다.

방정식이 T (N)가 = 2T (N/2) + n은 N

용액 그것이 T 의미 케이스 (2)를 충족 말한다 로그이다 (N) = Θ는 (N 로그 (N)).

n log (n)이 O (n) 일 수있는 방법을 모르겠다. n> 10 일 때 n log (n)이 n보다 커야하지 않습니까?

Answer 1

아니요, n 로그 n ≠ Θ (n). 이 표시에 따라 예고 그

LIM _{N → ∞} ((N, N 로그)/N) = LIM _{N → ∞} 로그 N = ∞

이 제한 무한대쪽으로 경향 때문에 , n log n이 Θ (n)이 아님을 알 수 있습니다. 그렇지 않다는 소식통을 찾았습니까?

희망이 도움이됩니다.

Answer 2

Θ (n⋅log (n))가 O (n)이 아닌 경우 O (n⋅log (n))가 올바른 해결책입니다.