0
$\begingroup$

Suppose I just invented merge sort, but due to my limited ability was only able to prove that the running time is $O(n^2)$. However, I suspect that the running time is actually better (in reality it's $O(n \log n)$).

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound (i.e. people generally think big O actually means big theta). Therefore, I am considering saying “runtime $\leq O(n^2)$”, even though it's technically redundant. Obviously I will explain in the text what I mean, but I'm saying it many times for different equations and I don't want to keep repeating myself.

I am aware of the definitions of big O, Omega, Theta, but which is clearer in a CS paper? The paper is related to machine learning.

$\endgroup$
  • 1
    $\begingroup$ This is probably opinion based, but if I were your reviewer I would be irked if you said $\le O(\cdot)$. Better add another sentence instead of uncommon notation. "We suspect this bound is not tight." or "We suspect none of these bounds is tight." is much clearer. $\endgroup$ – adrianN Oct 25 '16 at 7:36
4
$\begingroup$

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound

No, technically you should write "runtime $\in O(n^2)$".

I am considering saying “runtime $≤ O(n^2)$”, even though it's technically redundant

I don't think "redundant" is the right word. In a way, it makes even less sense than "$= O(\_)$"

While you can not control your readers' misconceptions, you can try not to feed them. Why not make explicit what you mean?

The running time is bounded by $O(n^2)$ but we suspect this bound can be improved to match the lower bound $\Omega(n \log n)$.

Or:

We have thus shown that the running time is in $\Omega(n \log n) \cap O(n^2)$.

In formulae, my advice is to always use "$\in$" unless you can give more precise results. For instance,

$\qquad C(n) = 2n\log n - n \pm O(\log n)$

would be okay.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.