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

Question

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.

Answer 1

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.