1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Mar 27 '17 at 20:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Mar 27 '17 at 20:37
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Mar 27 '17 at 20:38
  • $\begingroup$ @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) $\endgroup$ – Ravikant Mar 28 '17 at 5:48
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.