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

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?

• What do you mean by "this approach is incorrect"? What does "correct" mean for you? It sounds like both of you might be correct. Why do you think that what your advisor told you is wrong or inconsistent with your understanding? – D.W. Mar 27 '17 at 20:36
• Should you not be talking about "big $\Theta$" notation? The "big $O$" gives upper bounds, but you are shooting for actual approximation of running time, which is "big $\Theta$". For instance, if your program runs in time $4 \log X + \sqrt{Y}$ then it is in $O(X + Y)$, and you won't be able to fit that into a linear function. – Andrej Bauer Mar 27 '17 at 20:37
• Suggested background reading, to help you think through this and clarify your question: cs.stackexchange.com/q/857/755, cs.stackexchange.com/q/66815/755, cs.stackexchange.com/q/20186/755, cs.stackexchange.com/q/63361/755. – D.W. Mar 27 '17 at 20:38
• @D.W. I thought that the approach is incorrect because we are ignoring hardware dependent things in the equation (such as memory access patterns which has been rightly pointed out in the answer) – Ravikant Mar 28 '17 at 5:48

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.