Computational cost/complexity of algorithms based on the number of mathematical operations

Question

A problem is made up of $n$ similar parts. There is an algorithm $A_1$ to solve one of those parts using, for example, 10 divisions and 5 additions. Therefore, I apply the algorithm $A_1$ a total of $n$ times to solve the entire problem.

A different algorithm $A_2$ is available, which needs, for example, 5 divisions and 3 additions to solve each part. It must also be applied $n$ times to solve the whole problem.

Algorithm A2 is clearly better, since it performs fewer mathematical operations. However, using the O notation, both algorithms have the same computational cost. Is there a mathematical/computational way to clearly show that algorithm $A_2$ offers computational time/cost advantages over algorithm $A_1$?

Answer 1

Algorithm A2 is clearly better, since it performs fewer mathematical operations.

Which is far from true in the real world. Fewer operations is not equal to better, unless you assume that all operations perform exactly the same way (unrealistic) and the way you compose them (e.g. order of operations, even when commutative) doesn't affect performance (again: unrealistic). For example the x86 LOOP instruction is infamously known to be worse than multiple x86 instructions needed for manual loop. The difficulty of proper measurement gets higher when probability and/or multiple threads are involved.

In your very simple scenario it may be as you say because of the simplicity 10 divs + 5 adds vs 5 divs + 3 adds. But it still is possible that a compiler/cpu will optimize the first one better. We don't know what those algorithms actually are. For example what if those 10 divs are performed on constants and thus a compiler can simply replace them with a single constant? The devil is in details.

Finally it is very dangerous to generalize it to more complicated scenarios. The real world example is quick sort, which is known to even have worse complexity than other sorting algorithms, yet it is widely used, because in many practical situations it outperforms its (theoretically faster) competition.

Is there a mathematical/computational way to clearly show that algorithm $A_2$ offers computational time/cost advantages over algorithm $A_1$?

Typically people will benchmark algorithms (or rather their concrete implementations) in order to truely determine whether they perform better/worse. You will often see such benchmarks directly in published papers. Note that this is hard to do well, because there are so many factors one has to take into account (like for example cache locality, compiler optimizations, cpu optimizations, OS affecting runtime, etc.).

That being said some people do precise runtime analysis (as machine-independent as possible), e.g. Don Knuth in his book series “The Art of Computer Programming” or Robert Sedgewick in "Algorithms". However it is rather rare. At the end of the day we care more about practical application rather than theoretical numbers.

Answer 2

You are correct when you say that these are equivalent in the big-O sense. Each runs in time proportional to the input size $n$.

Assuming that the cost of those arithmetic operations is the same (although divisions are usually slower than additions), and that other parts of the computation are the same, the second is obviously faster. The loop will run almost twice as fast. There is no need for fancy mathematics. It's a straightforward inequality.

The point of the big-O analysis is to gain insight into how the algorithm will scale for really large inputs. If the code takes weeks to run with the first algorithm it will still be impractical with the second, even though it's twice as fast.