I am trying to understand the solution of sum of completion times. I found the following stuff in the link: Prompt Scheduling for Selfish Agents
Consider the case of a single queue, a selfish agent will simply join the queue immediately upon arrival, there is no reason to delay. Thus, jobs will be processed in first-in-first-out (FIFO) order. However, this may be quite bad in terms of the sum of completion times. Imagine a job with processing time L, arriving at time zero, followed by sqrt(L) jobs of length 1, all of which arrive immediately after the first. As the first job will only be done at time L, the sum of completion times for these 1 +sqrt(L) jobs is about L^(3/2)
I am able to understand the completion time of the above through a solution on the.stackExchange (Solution of Completion Times). Now I want to understand the running time of the shortest job first:
The paper says following (i.e. text2) immediately after the above text:
Contrawise, if the sqrt (L) length one jobs were processed before length L job, the sum of completion times would be about 2L. Obviously it seems a good idea to delay longer good idea to delay longer jobs and expedite shorter jobs.
I have tried following:
1 + 2 + 3 +………..+sqrt(L) + L
=(Sqrt(L) ( sqrt(L) + 1))/2 +L
=L/2 + sqr(L)/2 + L
I don't know how is it 2L as above in the paper text2.
Some body please guide me.
The actual sum of completion times is $$1+2+\dots+\sqrt L+\sqrt L+L$$ $$\sim\frac{\sqrt L(\sqrt L+1)}2+\sqrt L+L$$ $$=\frac{L+\sqrt L+2\sqrt L+2L}2=\frac32(L+\sqrt L)$$ To say it is "about $2L$" is providing an upper bound on this expression.