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

In summary: Segment TreeAlso, 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.
  • #1
zak100
462
11
TL;DR Summary
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.
 
Technology news on Phys.org
  • #2
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.
 
  • #3
zak100 said:
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)
 
  • Like
Likes zak100 and QuantumQuest
  • #4
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.
 
Last edited:
  • Like
Likes zak100
  • #5
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.
 

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

What is the FirstFit(FF) algorithm?

The FirstFit(FF) algorithm is a heuristic algorithm used in computer science for memory management. It allocates memory blocks to incoming processes by searching for the first available memory block that is large enough to hold the process.

What is the running time of the original FirstFit(FF) algorithm?

The running time of the original FirstFit(FF) algorithm is O(n), where n is the number of memory blocks. This means that the time taken to allocate a process increases linearly with the number of memory blocks.

What is the improved version of FirstFit(FF) algorithm?

The improved version of FirstFit(FF) algorithm is called BestFit(FF). It is similar to FirstFit(FF) but instead of allocating the first available memory block, it searches for the smallest available block that can hold the process. This results in more efficient memory usage and better performance.

What is the running time of the improved version of FirstFit(FF) algorithm?

The running time of the improved version of FirstFit(FF) algorithm is also O(n), as it still needs to search through all the memory blocks. However, it may have better performance due to more efficient memory usage.

What are the advantages of using the improved version of FirstFit(FF) algorithm?

The improved version of FirstFit(FF) algorithm, BestFit(FF), has several advantages. It can reduce memory fragmentation, resulting in better memory utilization. It also has the potential to allocate larger processes that may not have been possible with the original FirstFit(FF) algorithm. Additionally, it may have better overall performance compared to the original algorithm.

Similar threads

  • Programming and Computer Science
Replies
5
Views
884
  • Programming and Computer Science
Replies
2
Views
1K
  • Electrical Engineering
Replies
4
Views
944
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
2
Views
816
Replies
5
Views
994
  • Programming and Computer Science
Replies
0
Views
628
  • Engineering and Comp Sci Homework Help
Replies
9
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
3
Views
374
Back
Top