back
1 comments
> Doubling the input roughly doubles the time, the signature of an n log n algorithm.

Excuse me? This entire paragraph reads like the author has made the assumptions about the time complexity of the algorithms and pretends to discover them by simply timing the functions:

> List append tells a different story: 200,000 appends complete in 0.0071 seconds total, about 4e-08 seconds per operation, which is O(1) amortized.

1. You can't say anything about the time complexity after running the algorithm on a single input. This same exact reasoning would lead us to believe that sorting is O(1) per element because sorting the 200.000 elements took 0.5 seconds, which is 0.5/200000 seconds per element.

2. Even if we assume that we correctly measure list-append to be O(1), you can't just put "amortized" behind it without explaining how you get to that conclusion! Pushing to the front of a linked list is O(1), but that isn't an amortized time complexity.

I couldn't continue reading the article after that paragraph.