Running time of FirstFit(FF): Original and Improved version

[zak100]

TL;DR

Hi,
I am trying to understand the running time of FF algorithm

Hi,

I am trying to understand the running time of FF both the original and improved version. For the original version book says:

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 understand 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)

Kindly guide me is my understanding correct.

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.

 

[willem2]

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).

I don't understand why you multiply the times for searching and insertion to get O(log n log n).

O(n log n) is just the time to insert n items, if one item takes O(log n)

 

[QuantumQuest]

Summary:: Hi,
I am trying to understand the running time of FF algorithm

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 understand 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)

My question is, have you studied the pseudocode for this? I ask because, the way you write it, seems that you're trying to understand it somewhat in the abstract. This is not necessarily wrong but studying the pseudocode of an algorithm is helpful in any case and particularly when you have any doubt. If you study the pseudocode, you'll see in which case and why the running time of the FF algorithm yields an asymptotical $O(n^2)$.

In short, the worst case is the one in which a new bin has to be opened for each new insertion of an object.

Now, one very important use of this FF algorithm is as a partition selection algorithm in operating systems i.e. selecting free memory to accommodate a process. A high level way in which it works is: The OS looks at the whole of the sections of free memory. The process is allocated to the first hole found that is larger regarding the size of the process. If the size of the process matches the size of the hole then there is (obviously) no hole anymore otherwise the hole continues to exist but reduced by the size of the process.

First Fit is a fast method but not necessarily an optimal one.

Q.What is a segment tree above?

Segment Tree

Also, take note that the segment tree is not the only way to achieve $O(n\log n)$ worst-case running time. You can also use other heuristics as well, like a priority queue, to accommodate, for example, the bins with maximum remaining capacity so, effectively, you'll have one loop for objects and a priority quee for bins yielding an $O(n \cdot \log n)$ worst-case running time.

 

[zak100]

Hi,
Thanks for your answers. Priority queue example clearly explains why the running time is O(nlog n). However, I am using Allen Weiss and that book does not have pseudocode of FF.

Segment tree is a difficult concept. I would try to understand it at some other time.

Zulfi.