runtime - Is nlog(n) Big Theta(n)? Master Theorem -
is n⋅log(n) in Θ(n)? im asking because solving reccurrences using master theorem.
the equation t(n) = 2t(n/2) + n log n
the solution says fulfills case 2, meaning t(n) = Θ(n log(n)).
i don't understand how n log(n) o(n), shouldn't n log(n) greater n when n > 10?
no, n log n ≠ θ(n). see this, notice that
limn → ∞ ((n log n) / n) = limn → ∞ log n = ∞
since limit tends toward infinity, see n log n not θ(n). did find source says otherwise?
hope helps!
runtime big-o big-theta master-theorem
No comments:
Post a Comment