3 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 5y 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 5y agon^1.5 is still quadratic growth.
- mrfox321 5y agoQuadratic is literally x^2
- mwint 5y agoMy bad, it’s been a while since algorithms class. I had my orders mixed up.
- Yiin 5y agothe word you're looking for is exponential.
- zorgmonkey 5y agono the word you are looking for is polynomial, exponential is stuff like 2^n