Is it possible to have two adjacent busy nodes? Why or why not.

Question

In sequential style memory management (12.1), you start with one node accounting for all of memory. When memory is requested, a new node is created tracking the requested memory (busy) and the start and end positions of the original node are updated (free). After a request, “first-fit” says to find the first free node scanning left to right. “Best-fit” says to scan all the nodes and use the one closest to the requested size.

a) Is it possible to have two adjacent busy nodes? Why or why not.

b) Is it possible to have two adjacent free nodes? Why or why not.

c) What is the Big O of the Best-fit algorithm and why?

Summary

• Yes, it is possible to have two adjacent nodes busy in the case of both best-fit and first-fit algorithms.
• Yes, it is possible to have two adjacent nodes free in case of both best-fit and first-fit algorithms.
• The brute-force time complexity is O(n² ), but it can be optimized to a level of O(nlogn) time complexity.

Explanation

Yes, it is possible to have two adjacent busy nodes. As in both cases of first fit and optimal fit, after any busy node, we can have free memory available enough to satisfy the new request. In the beginning, also all the busy nodes will be adjacent, as there will be no fragmentation.

Yes, it’s possible to have two adjacent free nodes, as they track if the memory is free, so even if some memory is freed adjacent to a free node, that every node can be updated to represent a whole bigger node of free memory.

For optimal fit, we have O(N) as we need to scan all the nodes until the last to find the best fit for the requirement.