Simplification of Multi-variable Big-O Time Complexity

Question

I am attempting to calculate the Time Complexity of a function that sorts two arrays using Merge sort, finds their intersection and sorts the result from this intersection.

By analyzing the steps involved, I found the key steps to have time complexities of

O(a log a) + O(b log b) + O(a + b) + O((a+b)log(a+b))

where a is the size of the first array and b is the size of the second array

I further simplified this down to: O(a log a) + O(b log b) + O((a+b)log(a+b))

This is where I got stuck. But from what I have read, the idea of a + b being greater than both a and b allow me to remove the terms a log a and b log b. Using this, I got the overall Big O Notation as O((a+b)log(a+b)).

I am not sure if this is entirely correct though.

Answer 1

Your analysis is correct. Let me explain it more explicitly step by step if you are not sure about it.

Overall time complexity is: O(alog(a)) + O(blog(b)) + O(alog(a+b) + blog(a+b)).
Logarithm is a strictly increasing function on x > 0, that is, log(x) > log(y) iff x > y > 0.
Input size cannot be negative, therefore for our analysis we can use this fact.
Using this property, we know that log(a+b) > log(a), therefore alog(a+b) > alog(a).
We can conclude that O(a log(a)) is a subset of O(a log(a+b)) since every algorithm upper-bounded by alog(a) as input size goes to infinity is also upper-bounded by a log(a+b).
Therefore we can get rid of O(a log(a)).
Apply the same logic for O(b log(b)).
At the end, we have O(alog(a+b) + blog(a+b)), which corresponds to O((a+b)log(a+b)).