Is O(log n) + O(log n) = O(n)? [duplicate]

Question

This question already has answers here:

What is O(…) and how do I calculate it? (2 answers)

Closed 5 years ago.

We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity?

For example, if I have a method to calculate the first occurrence of a number in a sorted array with duplicates and another method to calculate the last occurrence. Each of both methods takes O(log n) to run, so at the end if I want to know the number of occurrences of an specific number in the array using both methods I would have a O(2 log n), right? Can we infer that O(2 log n) is equal to O(n) or lower?

Answer 1

No, 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)

where k is a constant, non-zero factor and g is a bounding function.

An 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 O(log n).

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 log₂(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 O(n).

Answer 2

Both O(log n) and O(2 log n) are subsets of O(n). They are also both equal to O(log n).

You must remember that O(log n) is a set, it is (informally) "the set of all functions that don't grow significantly faster than f(x) = log x". So, all of the following are true

• O(log n) = O(2 log n)
• O(log n) ⊂ O(n)
• O(2 log n) ⊂ O(n)
• ∀f: f ∈ O(2 log n) ⇒ f ∈ O(n)

You can easily verify that by plugging the functions into the definition of O(g).

Unfortunately, there is a lot of abuse of notation going on in this regard. For example, f ∈ O(g) is often written f = O(g), even though it doesn't make sense: f is a function, O(g) is a set of functions. An apple can never be equal to a set of apples! Likewise, it is often written that O(f) = O(g), when what is really meant is that O(f) ⊂ O(g). And lastly, people will sometimes claim that f(n) = 2n is an element of O(n) but not of O(n²), which is wrong. O(n) is a subset of O(n²), so any function that is in O(n) is also in O(n²).

Answer 3

For large values of n, the constants are ignored in Big O notation.

Hence

O(log n)+O(log n)=O(2log n)->O(log n)