CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
王亦舟
王亦舟

Reputation: 141

The sum of theta notation and Big o notation

Was wondering if I have a algorithm which has two parts with known runtime of theta(nlogn) and O(n). So the total runtime goes to theta(nlogn) + O(n)

To my knowledge, if for either the sum of two BigOh Notations or the sum of theta notations, we always use the max value of each.

While in this case, as the worst runtime for the part O(n) is anyway smaller than the part theta(nlogn), can I assume the runtime of this algorithm is theta(nlogn)?

Thanks!

Upvotes: 2

Views: 889

Answers (1)

templatetypedef
templatetypedef

Reputation: 373452

Yep, that’s correct. Regardless of whether the O(n) term is tight or not, it’s still a low-order term compared with Θ(n log n).

Upvotes: 3

Related Questions