How do you show that one algorithm is more efficient than another algorithm?

Question

I'm no professional programmer and I don't study it. I'm an aerospace student and did a numeric method for my diploma thesis and also coded a program to prove that it works.

I did several methods and implemented several algorithms and tried to show the proofs why different situations needed their own algorithm to solve the task.

I did this proof with a mathematical approach, but some algorithm was so specific that I do know what they do and they do it right, but it was very hard to find a mathematical function or something to show how many iterations or loops it has to do until it finishes.

So, I would like to know how you do this comparison. Do you also present a mathematical function, or do you just do a speedtest of both algorithms, and if you do it mathematically, how do you do that? Do you learn this during your university studies, or how?

Thank you in advance, Andreas

Answer 1

The standard way of comparing different algorithms is by comparing their complexity using Big O notation. In practice you would of course also benchmark the algorithms.

As an example the sorting algorithms bubble sort and heap sort has complexity O(n²) and O(n log n) respective.

As a final note it's very hard to construct representative benchmarks, see this interesting post from Christer Ericsson on the subject.