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.