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 Answer
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))
O(n)andO(m logn(n))are using the samen? If not then you have to rename one of thenvariables, For exampleO(k)andO(m log(n))can becomeO(k+ m log(n))It could also be that thenin the first formula is ``m` in the second — we're not given context to know one way or the other.