in reply to Re^2: Algorithm complexity
in thread Algorithm complexity

But you can tell that a program didn't finish after a given threshold (a week or so) without violating Turing's laws.

Yes, that's an incomplete solution. Which doesn't tell you anything about the asymptotic runtime if it didn't finish.

In theory it should be possible to approximate O(n) by benchmarking for increasing n and using numerical methods to interpolate the gotten data.

If you don't try it for all possible inputs you can miss worst case scenarios.

For example old versions of perl used to have an O(n) complexity for hash accesses if the keys followed a certain pattern that lead to 100% hash collisions - which was an attack vector for denial of service attacks.

(Newer perl versions solve that by randomizing hash seeds if too many collisions occur).

You not only have to specify what n in O(n) means, but also if you're talking about worst case, average case or amortized runtime.

Replies are listed 'Best First'.
Re^4: Algorithm complexity
by LanX (Saint) on Jul 08, 2009 at 00:45 UTC
    Well it's only approximation and as I said implies waiting for "enough" time. I doubt that waiting for weeks is considered practicable for a reasonable accuracy of the numerical calculations! (since these calculations rely on leveraging effects of multiple runs 8 )

    (OTOH the sheer fact that you have to wait too long already gives you information that the tested algorithm might not be what you wanted).

    But you're right, worst case complexity is far less practicable, because this implies checking _all_ cases. And worst case is what you normally want to be expressed by the Landau symbol.

    Cheers Rolf

[reply]
      I think there are many problems which we don't have efficient algorithms for. There are even some problems to which the known algorithms take so much time that it would be almost impossible for you to get the data needed to plot it and then use numerical methods. One such example are Wiefrich primes for which only 1 pair is known to this date. Can you apply your numerical methods to 1 point on a chart ?
[reply]
        Lets suppose a brute-force algorithm testing all numbers up to n. (don't wanna complicate it by restricting it to primes)

        After a week and testing 10^x numbers you'll get 2 correct Wieferich primes and the information that calculating a third prime bigger than 10^x takes at least 10^x steps.

        That's an empiric lower bound for the complexity, you can tell that this brute-force approach is at best O(n) for n<10^x, which is quite accurate!

        OK, this example is a little bit too trivial, since it's a decision problem.

        You actually have 10^x points and not only 2 !

        Cheers Rolf

[reply]

In Section Seekers of Perl Wisdom