News for hackers. Stuff that matters.

A comment on Two workers are quadratically better than one (2020).

Re:Two workers are quadratically better than one (2020) by williamkuszmaul on Monday May 02, 2022 @06:27PM (#31241858)
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.

[ Parent | on HN ]
Re:Two workers are quadratically better than one (2020) by mwint on Monday May 02, 2022 @10:43PM (#31243853)
n^1.5 is still quadratic growth.
[ Parent | on HN ]
Re:Two workers are quadratically better than one (2020) by mrfox321 on Monday May 02, 2022 @11:04PM (#31244013)
Quadratic is literally x^2
[ Parent | on HN ]
Re:Two workers are quadratically better than one (2020) by mwint on Tuesday May 03, 2022 @07:22PM (#31254880)
My bad, it’s been a while since algorithms class. I had my orders mixed up.
[ Parent | on HN ]
Re:Two workers are quadratically better than one (2020) by Yiin on Tuesday May 03, 2022 @04:43AM (#31246080)
the word you're looking for is exponential.
[ Parent | on HN ]
Re:Two workers are quadratically better than one (2020) by zorgmonkey on Tuesday May 03, 2022 @05:15AM (#31246265)
no the word you are looking for is polynomial, exponential is stuff like 2^n
[ Parent | on HN ]