The Student Room Group

D1 Question - Order of an algorithm

Here's the question:
'Explain why the first-fit bin packing algorithm has a quadratic order.'

The online answers page says this:
Screenshot_2020-05-10 Microsoft Word - alevelsb_d1_ex1f docx - alevelsb_dm1_ex1f pdf.png

So in other words, we're going from k items requires k-1 comparisons to plucking a magical formula out of thin air without any explanation.

k items, I get that. k-1, I get where they are coming from. 1/2n(n-1), I do not get that AT ALL.

What I want is a METHOD to how they've gotten from k and k-1 to n(n-1)/2. Please someone, fill in the gaps. Thankyou.
Reply 1
Original post by MeatFeastMan
Here's the question:
'Explain why the first-fit bin packing algorithm has a quadratic order.'

The online answers page says this:
Screenshot_2020-05-10 Microsoft Word - alevelsb_d1_ex1f docx - alevelsb_dm1_ex1f pdf.png

So in other words, we're going from k items requires k-1 comparisons to plucking a magical formula out of thin air without any explanation.

k items, I get that. k-1, I get where they are coming from. 1/2n(n-1), I do not get that AT ALL.

What I want is a METHOD to how they've gotten from k and k-1 to n(n-1)/2. Please someone, fill in the gaps. Thankyou.

The sum of a linear expression is quadratic, but
0 + 1 + 2 '+ ... + (n-1)
where there are n terms is the average value * n.
Average of each pair of terms is (n-1)/2
So
n*(n-1)/2

Alternatively, use the standard results for
Sum (k-1) = Sum k - Sum 1 = n(n+1)/2 - n = n(n-1)/2
I think it comes from standard series summations...
Sum of k from 1 to n is n(n+1)/2 = 0.5n^2 +0.5n
Sum of 1 from 1 to n is n
So the sum of k-1 from 1 to n is 0.5n^2 +0.5n -n = 0.5n^2 - 0.5n = n(n-1)/2
Idk if you want a proof of the standard series results as well but I imagine that's where it comes from (I'm no expert but that's my instinct)

Quick Reply

Latest