3 ms·

Also using big-O notation turns the "1/2" of the post title into a discarded constant.

• mrguyorama 4y ago
  My algorithms class discussed the importance of not forgetting the constants. We talked about an algorithm for recursively taking averages of a list of numbers (or whatever that's not important) that was O(n^2) but only in worst case, while there was a version that is guaranteed O(nlogn) or something but the constant factor was 27. This meant the growth only mattered in extreme cases.
  • karmakaze 4y ago
    That math doesn't seem to check out. Say with base-2 log and a 27 factor difference, for 1000 it would be 1000^2 = 1,000,000 vs 27 * 1000 x log 1000 = 270,000. I wouldn't call n=1000 an extreme case for most problems. Just because practical counterexamples exist, don't think that it applies to your problem unless demonstratably so, an then still worry about N being larger than originally designed for.