4 ms·
I'm not sure why they claim that the total time grows quadratically. If tasks arrive arrive randomly at the same average rate as they can be processed, then th
by williamkuszmaul 4y ago
I'm not sure why they claim that the total time grows quadratically.
If tasks arrive arrive randomly at the same average rate as they can be processed, then the amount of time that the nth task will have to wait is proportional to sqrt(n) in expectation. So one would expect a total waiting time of n^1.5, which incidentally fits much better to their plotted curve than n^2 does.
- mwint 4y agon^1.5 is still quadratic growth.
- mrfox321 4y agoQuadratic is literally x^2
- mwint 4y agoMy bad, it’s been a while since algorithms class. I had my orders mixed up.
- Yiin 4y agothe word you're looking for is exponential.
- zorgmonkey 4y agono the word you are looking for is polynomial, exponential is stuff like 2^n