What is the difference between $O(n + \log n)$ and $O(n + n/2)$?

47 Views Asked by At

I've learned that when we see O(log n) we consider that a given problem is halve every time. So having O(n + log n) would be that we first iterate n times once and then the problem is continually halved until resolution.

Does O(n + n/2) = O(3/2 n) mean the same thing except that the problem is halved once after iterating n times once aswell?

1

There are 1 best solutions below

0
On

Using your mental model, $O(\log(n))$ does not mean that "the problem is halved every time", that would rather correspond to $O(n+n/2+n/4+n/8\cdots)=O(2n)$.


Technically, $O(n+\log(n))$ and $O(n+n/2)$ are both equivalent to $O(n)$, they make no difference. In fact, you cannot decompose the processing precisely in distinct phases by just looking at the asymptotic complexity. The Big-O notation is just a global result.


Possible interpretations:

  • $O(\log(n))$: the problem size (i.e. the number of elements) is halved iteratively, but only a constant number of elements is processed every time.

  • $O(\sqrt n)$: the elements are arranged in a square, and a single row of the square is processed.

  • $O(n)$: every element is processed a constant number of times. Alternatively, the data set is processed in successive $O(n)$ passes, and gets halved on every pass.

  • $O(n\log(n))$: the data set is processed in successive passes while the number of elements remains unchanged. The number of passes is determined by repeatedly halving the size, though all elements are kept.

  • $O(n^2)$: every pair of elements is processed.