The sum of theta notation and Big o notation

user_12143806 0
Viewed 334

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!

big-o complexity-theory time-complexity algorithm
1 Answers

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).

user_5015570
Related