Rendered at 23:55:08 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
atiedebee 3 hours ago [-]
> 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.
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.