Jump to content

FirstFit (FF) Running Time: Original and Improved version


Recommended Posts

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.

Link to post
Share on other sites

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.

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.