Difference between graphs and asymptotic analysis to compare running times of an algorithm

Question

The question pretty much states what i'm asking for.

I have an algorithm and I was wandering what is the better approach to achieve ah 'Big-Oh' running time - through a graph and plotting the number of input against the running time, or through asymptotic analysis?

For my graph I'm currently using:

private int startTime = System.currentTimeMillis(); //At start of algorithm
private int endTime = System.currentTimeMillis(); //At the end of algorithm
int runningTime = endTime - startTime;

What's the difference between both methods of 'measuring' the running time of an alogrithm?

Answer 1

The problem with the "empiric" (plot the run time against size of input), is it only work for the provided test case.

The "theoretic" analysis gives you all pitfalls of the algorithm, you can analyze the true best case/ average case/... using math, and it is guaranteed to be correct.

A good common example is the simplex algorithm, which is quite fast usually, but does have occasional exponential worst case run time for some inputs.

On the other hand, due to asymptotic analysis ignoring constants, and only apply for "large enough inputs", they are pretty much useless if the input is expected to be relatively small, and it is hard to distinguish between 2 algorithms in the same complexity class, but with different constants, and constant do matter in production code.

tl;dr: each got its own usage, and combining both gives better results than using only one of them.

As a side note, when using the empirical method, be sure to use statistical tools, and statistical hypothesis testing specifically before making conclusions. Also, always remember that the empirical tools are only valid for the class of problem you checked (so if you don't check for a sorted array for example, you won't know quicksort might take significantly longer time if it encounters one).