FirstFit (FF) Running Time: Original and Improved version

[zak100]

Hi,

First I want to discuss the running time of original version. Form the book (Allen Weiss), I found: 

Quote

A simple method of implementing first fit would process each item by scanning down the list of bins sequentially. This would take O(n^2).

What I understood from this that before placing the items, FF traverses all the bins from beginning to end i.e. n bins. Now each bin can have n items, because of that the running time is O(n^2).

 

Somebody please guide me is the above version correct or not.

 

Zulfi.

[zak100]

Hi,
I am now discussing the improved version:

I found the improved version here:

First Fit Tree Version (Improved Running time)
 

We would like to reduce the time needed to find the first (leftmost) bin where the current item can fit, which required O(n) time per item. To achieve this goal we can use a segment tree for maximum range queries on the remaining bin spaces. This way every time a new item is given we can go down the segment tree and find the bin that we should use in O(logn) time for each item. So the computatonal complexity of the algorithm drops down to O(nlogn)

Q.What is a segment tree above?

I can't understand the running time of this tree version. In case of tree version, searching should take O(log n) and insertion should take O(log n).

So the total running time should be O(log n log n).

Somebody please guide me why the running time is: O (n log n).

Zulfi.

[Strange]

7 minutes ago, zak100 said:

Q.What is a segment tree above?

https://en.wikipedia.org/wiki/Segment_tree

[zak100]

Hi,

Thanks.

The running time is O(n log n) because they are using  segment array whose running time is O(n log n).

 

I think my answer is correct.

Zulfi.