3 ms·

It's not 945x faster, it's O(N) faster.

• nayuki 7y ago
  Indeed, it's an example of "Shlemiel the Painter's Algorithm". https://en.wikichip.org/wiki/schlemiel_the_painter%27s_algorithm https://en.wikichip.org/wiki/schlemiel_the_painter%27s_algor...
• deleted 7y ago
  [deleted]
• StreamBright 7y ago
  945x is the actual measured difference, O(N) is the theoretical difference. Many times quadratic time complexity is ok because you are working on very small N.
  • olliej 7y ago
    The point is 945x is just the measurement for this particular test case. If the author made the test larger it would appear even faster. This is the underlying problem with people who don’t understand what big-O complexity is saying.
  • rat9988 7y ago
    I believe he means it's 945x faster in the current case, but O(N) in the general case.