On Wednesday, 12 June 2019 at 06:57:55 UTC, Robert M. Münch wrote:
If you use an associative array or a set, it's O(n) time and O(n) space.I don't see how this is the case. The AA itself has some overhead too. So, the checking loop is O(n) but the AA lookups not.
Hash table insertion and lookup lookup both have amortized O(1) complexity, and D's associative arrays are implemented using hash tables.
