# Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight?

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.

• 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. Commented Oct 25, 2016 at 7:36

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.