3

I'm doing a running time analysis using the aggregate method and I'm a bit confused about what would be the result in this case. I have some intuition in inferring that it would be O(mlog(n)) but I'm not sure

1
  • 1
    Do you know that O(n) and O(m logn(n)) are using the same n? If not then you have to rename one of the n variables, For example O(k) and O(m log(n)) can become O(k+ m log(n)) It could also be that the n in the first formula is ``m` in the second — we're not given context to know one way or the other.
    – Erik Eidt
    Commented Apr 12, 2023 at 17:46

1 Answer 1

8

You can have + in big-o, when you have terms with different parameters.

O(n + mlog(n)) describes the general case where n and m are different terms, that grow independantly.

In the case where n is fixed, that is equivalent to O(m). In the case where m is fixed, that is equivalent to O(n). In the case where n is proportional to m, it is O(nlog(n))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.