Can we use Big O notation to predict actual running time of the algorithm on machine?

Question

As per my understanding, a program can take a different amount of time to run on different machines because it is dependent on hardware. So we use big O notation which is independent of hardware to compare the performance of two algorithms as the input grows.

I am working on an algorithm which has a complexity of $O( X + Y )$ and it takes a number as an input. My advisor has asked me to collect actual runtime(on the same machine) of the algorithm with different numbers as an input. Then determine coefficients a, b and c such that

$runtime=a.X + b.Y + c$

and use this equation to predict runtime for other inputs. (for instance, consider BFS, in which case $X$ and $Y$ could be replaced by $V$ and $E$ and it takes a source vertex as an input. Now I am asked to record runtimes of the BFS execution using different source vertices as an input and determine the coefficients. The claim is, using the same hardware and same graph but different source vertex I should be able to get a good approximation of the runtime.)

As per my understanding, this approach is incorrect as big O notations are meant for comparison, as the input grows. But my advisor argued that big o notation captures all the operations in the code and therefore there must exist coefficients a,b,c such that the above equation gives a good approximation.

Is the claim made in the above argument is correct?

Answer 1

I'll give you an example where it unexpectedly goes totally wrong:

Write a program that calculates the product of two square matrices with real values, stored as double precision numbers. Use the straightforward algorithm where c [i, j] = sum of a [i,k] * b [k,j]. Measure and print the time for say n = 1 to n = 1000 (this will take a while). The time is $\Theta(n^3)$, so if r (n) is the measured time, you are interested in $c_n$ where $c_n$ is defined by $r (n) = c_n·n^3$.

You will find several interesting effects. You might expect that $c_n$ is quite large for n = 1, 2, 3 etc. because all the overheads are quite large compared to $n^3$, and at some point $c_n$ stays quite unchanged.

If you learned about cache memory, you will realise that a modern processor may have say 64KByte of very fast L1 cache, maybe 256KByte of fast L2 cache, say 4M of not so fast L3 cache, and uncached memory is quite slow. So as n grows, $c_n$ will jump up every time the memory used exceeds one of those cache limits.

But there are worse problems: The naive algorithm uses a really bad pattern to access memory, but how bad it is depends on particular values of n. Worst case is n = multiple of a large power of 2. You can expect the runtime for n = 128 to be massively larger than for n = 127 or n = 129.

So I'd say your advisor is completely wrong.

Answer 2

Big O is for worst case, but here it seems like you are more interested in average case? It is not really clear how the worst case complexity relates to your measurement, not only for the type of reasons gnasher729 described (caching, branch prediction(!)).

For example:

Quicksort is worstcase O(n^2), but the average case is O(n*log(n)). When you sample the input space and try to fit parameters for a*n^2 + b with measured parameters from a function a*n*log(n) + b (because what you are doing is more likely to get you average case results), I would not expect sensible predictions.

If worst case vs. average case is no issue, then maybe it is sensible, but only for

1. large inputs, to avoid the technical issues gnasher729 mentions, which will mostly go away once you are big enough that everything is bad and slow. Also, since Big O talks about the limit, it makes sense that the approximated function will only work well for big inputs.
2. many, diverse, examples. To fit anything well you need many examples.