Jump to content
Sign in to follow this  
zak100

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.

Share this post


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.

Share this post


Link to post
Share on other sites

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.

Share this post


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
Sign in to follow this  

×
×
  • 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.