zak100 3 Posted April 23, 2020 Share Posted April 23, 2020 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

zak100 3 Posted April 23, 2020 Author Share Posted April 23, 2020 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

Strange 4273 Posted April 23, 2020 Share Posted April 23, 2020 7 minutes ago, zak100 said: Q.What is a segment tree above? https://en.wikipedia.org/wiki/Segment_tree 1 Link to post Share on other sites

zak100 3 Posted April 23, 2020 Author Share Posted April 23, 2020 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. Link to post Share on other sites

## Recommended Posts

## 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