O(log n) + O(log n) is not
O(n). It is still
O(log n). When we have a big-O formula multiplied by a constant, it is equivalent to the value without the multiplied constant. So:
O(k * g) = O(g)
k is a constant, non-zero factor and
g is a bounding function.
O(log n) operation is an operation that takes a number of steps proportional to the logarithm (the base just contributes a constant factor) of the size of the input, denoted by
n. When you have multiple operations of the same big-O order, you can add them together as you have done, and come out with something like
O(2 * log n), but big-O notation is not concerned with constant multiplicative factors, so we ignore the 2 and write
The reason we are not concerned with constant factors* is that we are examining an algorithm's potential for growth based on input size. We don't use it to calculate the exact number of steps, just to see how the number of steps might grow.
Let's look at some real numbers to give ourselves a less mathematically abstract example. We have an algorithm that runs in
O(log n) time and takes exactly log2(n) steps. We have a method where we run it once with an input of size 8. It takes 3 steps to complete. We have another method where we run it twice, so it takes 6 steps to complete. This is not the comparison we care about, though. We want to know about the growth. We run the first method again with an input size of 16. It takes 4 steps to complete, +33% more steps. We run the second method with an input size of 16. It takes 8 steps to complete, also +33% more steps. We can see that, though the number of steps is different, the growth is the same between the functions. The rate of growth is
O(log n) despite how many times it is called, and it is the rate of growth that we are interested in.
* We are also not concerned with lower-growth bounding function parts, so
O(n + log n) is equivalent to