Hacker News new | ask | show | jobs
by baobabKoodaa 1762 days ago
No? If you check your own sources, you will find that this is precisely the type of case where a developer is using an O(n^2) algorithm out of ignorance when they should have been using a faster algorithm, and that the high load time was caused by this mistake. The time complexity for bubble sort is also O(n^2), compared to O(nlogn) for reasonable sort algorithms. I don't really understand how you take all this information and then conclude "no".
1 comments
jcranmer 1762 days ago
The way accidental O(N²) comes about isn't "I'm intentionally using an algorithm that's O(N²)" (e.g., bubble sort), but "this method that I think is O(1) is actually O(N)" (whether because it's badly designed or just badly documented).

It's really not in the same vein as using bubblesort instead of a mergesort: failures aren't in algorithm design but in the actual mechanics of the implementation that is ancillary to the algorithm itself.

link
baobabKoodaa 1762 days ago
> failures aren't in algorithm design but in the actual mechanics of the implementation that is ancillary to the algorithm itself.

Strongly disagree. The GTA developer basically designed an algorithm which loops items in an array, and for each iteration in the loop, they parse the entire JSON that contains all items, and they do lookups for duplicates from an array instead of from a set. This is like a quintessential example of an algorithm design failure, so it seems weird to me that you're not attributing it to a failure in algorithm design, but instead you pass the buck to creators of the library that the developer was using. Sure, the library methods could have been documented better, or implemented differently, or whatever, but that seems like an entirely unrelated discussion.

> "this method that I think is O(1) is actually O(N)"

I'm fairly certain the developer in question does not understand / care what big-O notation means. Therefore, this almost certainly is not the thought process that lead to the slow load times in GTA. More likely the developer was just mashing things together until "it works".

link