Why is `O(log n) + O(log n) = O(log n)`

October 9, 2024

I was thinking about this recently while doing some Leetcode binary search problems. For this particular problem I split it up into two sub problems, each of which used binary search.

This Stack Overflow answer explains it nicely. Constant, multiplicative factors don’t matter much for Big O notation. So the sub problems can also be thought of as O(2 * log n), where the constant factor of 2 doesn’t matter.

During this exercise I also came across a cool graphing tool called Desmos which could be very handy for visualizing and intuitively understanding some of these concepts.