search

kolodny / exercises

Some basic javascript coding challenges and interview questions
4.23k stars 672 forks source link

Example "sort sorts better than n^2" doesn't actually verify the algorithm's time complexity #38

Open davidrunger opened 9 years ago

davidrunger commented 9 years ago

Someone not familiar with time complexity might see that this spec is passing and assume that their algorithm is less than O(n^2), when in fact the algorithm might be O(n^2) or worse.

I would think it would be better to just call the spec "sort... can sort a large array" or something.

Or, on the other hand, maybe you actually could do something to verify the time complexity, along the lines of what is in the binary-search "uses a divide and conquer algorithm" example, maybe?

kolodny commented 9 years ago

Very true, maybe implment something like what the binary search test does in that it checks how often values are accessed https://github.com/kolodny/exercises/blob/master/binary-search/test.js#L56