1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ $O(0)$ contains only functions, which are constantly $0$ after some finite steps. $\endgroup$
    – zkutch
    Jan 9 at 12:30
2
$\begingroup$

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.

$\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.