0

I've seen in many places that the time complexity of merging 2 n-sized sorted arrays is O(n). Isn't Θ(n) more accurate here?

Thanks in advance!

Ben
  • 33
  • 2
  • 3
    That's right, but these two notations are often used to mean the same thing even though they're different. `Θ(f(n))` is always more accurate than `O(f(n))` by the way (see https://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on) – Dici Sep 09 '18 at 19:27
  • Possible duplicate of [What is the difference between Θ(n) and O(n)?](https://stackoverflow.com/q/471199) – Bernhard Barker Sep 10 '18 at 00:16

1 Answers1

3

Proving Θ(f(x)) is more difficult than proving O(f(x)) so many people don't bother. However, in this case it is actually correct that in-place merging two n-sized sorted lists is O(n) for all possible inputs and not Θ(n).

Obviously, copy-merging two n-sized lists can't be better than O(n), because 2*n elements are being copied. However, in-place merging can be implemented in Ω(1) for best case scenarios. This is a simple case when all elements of the first list are smaller or equal to elements in the second list. A merging algorithm can detect this situation in O(1) and do nothing if the elements are already in the correct order, hence Ω(1) for best case.

Conclusion: in-place merging is not Θ(n), but is Ω(1) instead. Actually, in-place merging with additional memory can be Ω(1) and O(n), but without additional memory it takes O(n log n) to merge two n-sized lists, so obviously the question is not about this case.

That's why it is simpler just to say O(n) and not be bothered with the details of in-place vs. copy merging. Also, usually what bothers programmers are the worst case, and the average case, not the best case.

edit 1

In many cases when people say O(f(n)) they mean Θ(f(n)) worst-case complexity. In-place merging is also Θ(n) for the worst case, just like copy-merging.

edit 2

People usually refer to all possible runs when they talk about complexity. If worst case is Θ(f(x)) and best case is Θ(g(x)), then it is technically correct to write that O(f(x)) and Ω(g(x)) are tight for all possible cases.

Similarly, if copying an array is Θ(n), there is no sense saying that it is O(2n). That would be technically correct, but a very uncommon use of the big O notation.

Michael Veksler
  • 8,217
  • 1
  • 20
  • 33
  • 1
    This is true, but we can still say that in-place merging's worst-case complexity is Θ(*n*). – ruakh Sep 09 '18 at 20:29
  • @ruakh: obviously, for example if no element is at its final place. –  Sep 09 '18 at 20:33
  • @YvesDaoust: You say "obviously", but I think this answer is overlooking/ignoring it. (Hence my comment.) – ruakh Sep 09 '18 at 20:54
  • @ruakh I also think this is obvious. It is rare when the big theta notation for the worst case. Actually, if it is possible to formulate big theta expression for worst case, then that expression is usually used for big O as well. Anyway, I've updated the answer – Michael Veksler Sep 09 '18 at 21:04
  • @ruakh: you didn't mention the worst-case in your post, so the answer needn't address it. –  Sep 09 '18 at 21:04
  • @YvesDaoust: I'm not sure what you mean by "in your post". (Are you confusing me with the OP? If so, then -- pro tip: any answers or comments by the OP have a blue background behind the signature.) – ruakh Sep 09 '18 at 22:55
  • To answer the OP's question another way: The reason that big-theta isn't used more often is that it leads to discussions like this one ;-) – Matt Timmermans Sep 09 '18 at 23:14
  • 2
    You seem to be using Omega to refer to best-case and Big-O to refer to worst-case. But any of these notations can, in fact, refer to any of best-, worst- or average-case. See: [How do O and Ω relate to worst and best case?](https://cs.stackexchange.com/q/23068) – Bernhard Barker Sep 10 '18 at 00:22
  • @dukeling, this usage is common. Usually in CS people use big O as a tight bound. I have never seen anybody write that copying an array is O(2^n), although technically correct. Usually people use big O to refer to a tight bound of worse case. This is correct, since this is an upper bound for all possible inputs, but O is missing the fact that it is tight – Michael Veksler Sep 10 '18 at 04:58
  • This discussion reminds me of a joke about two guys that get drifted away in a hot balloon and then spot someone on the ground. "Where are we?" they ask the ground walker, "in a hot balloon, 30 feet above ground" he answers. "You must be a mathematician" say they, "how do you know?" he replies. "Your answers are accurate but useless". People usually use big O and big Omega to refer to all possible runs, not just best or worse case. This is a comm practice, even if not strictly correct. – Michael Veksler Sep 10 '18 at 05:10
  • I added clarifications to make sure that there is no misunderstanding regarding best-case, worst-case, and all cases. – Michael Veksler Sep 10 '18 at 05:24
  • @ruakh: sorry for the confusion. –  Sep 10 '18 at 06:51