So I know the Next Fit Bin Packing algorithm is bounded by two times the optimal solution for the problem, but I can not think of an order of arriving elements that actually takes twice the number of bins necessary.
Something like:
50 -> 25 -> 50 -> 25 -> 50 -> 25 -> 50 -> 25
would result in:
|25| |25| |25| |25|
|50| |50| |50| |50|
bins with next fit while the optimal solution would be:
|50| |50| |25 * 2|
|50| |50| |25 * 2|
Which is only one bin difference. So what actually is the worst order of elements for the next fit bin packing algorithm?