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.

In reply to Re^3: Algorithm complexity by moritz
in thread Algorithm complexity by fauria

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.