# Whether and how to distinguish two kinds of $O(1)$ speedup

Here is a very bad algorithm that computes $$4n$$ for an integer input.

# Original algorithm
function fourtimes(n)
two = 1 + 1
res = 0

for i in 1:n
res += two
res += two
end

return res
end


Here is one way of improving the algorithm (speedup A).

# Speedup A
function fourtimes(n)
two = 2
res = 0

for i in 1:n
res += two
res += two
end

return res
end


Here is another way of improving the algorithm (speedup B).

# Speedup B
function fourtimes(n)
four = 2 + 2
res = 0

for i in 1:n
res += four
end

return res
end


The original algorithm is $$O(n)$$, and both speedup A and speedup B leave this overall complexity the same. Thus, I am inclined to call both of these $$O(1)$$-speedups.

On the other hand, for large $$n$$, speedup A is barely noticeable, whereas speedup B cuts the computation time in half. If the original algorithm takes $$1n$$ units of time to compute, then speedup A takes $$1n - \epsilon$$ units, whereas speedup B takes $$\frac{1}{2}n$$ units.

I am wondering if there is a way to express mathematically that speedup B is a more significant improvement than speedup A over the original algorithm—or is it?

If so, can the difference be expressed in big-O notation?

Would it be appropriate to abuse notation and call A an $$O(0)$$-speedup instead?

• $O(0)$ contains only functions, which are constantly $0$ after some finite steps. Jan 9 at 12:30

We can analyze the number of arithmetic operations as a function of $$n$$. Let us call the algorithms O (for "original"), A (for "speedup A") and B (for "speedup B").
Let us denote by $$f_X(n)$$ the number of additions performed by algorithm X. We have that
• $$f_O(n) = 1 + 3n$$,
• $$f_A(n) = 0 + 3n$$, and
• $$f_B(n) = 1 + 2n$$.
So the only improvement of A over O is that it avoids computing 1 + 1 by initializing two to 2 directly. On the other hand, B is even better as it does one operation less for each round of the loop.
This is a mathematically sound way of expressing that B gives us a more significant saving than A, which is what you wanted. So in particular, there is no need to express any of the $$f_X$$ in terms of Big Oh. It's good to be as precise as possible whenever you can and it makes sense.