zak100 said:
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.
zak100 said:
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.