Bird
Raised Fist0

What is the time complexity of performing memory compaction in a system with n allocated blocks and total memory size M?

medium🪤 Complexity Trap Q5 of Q15
Operating Systems - Internal vs External Fragmentation - Compaction & Buddy System
What is the time complexity of performing memory compaction in a system with n allocated blocks and total memory size M?
AO(1) since compaction is a hardware-supported operation
BO(n) because only allocated blocks are moved
CO(log n) due to hierarchical merging of free blocks
DO(M) because compaction involves shifting memory contents across the entire address space
Step-by-Step Solution
Solution:

  1. Step 1: Understand compaction process

    Compaction shifts allocated blocks to one end, moving memory contents physically.

  2. Step 2: Analyze complexity factors

    Shifting involves moving data proportional to total memory size M, not just number of blocks n.

  3. Step 3: Evaluate options

    O(M) because compaction involves shifting memory contents across the entire address space is correct because moving blocks involves moving their data, not just metadata; O(log n) due to hierarchical merging of free blocks is unrelated to compaction; O(1) since compaction is a hardware-supported operation is false as compaction is software-driven and costly.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Compaction moves memory contents proportional to M [OK]
Quick Trick: Compaction moves data proportional to total memory size [OK]
Common Mistakes:
MISTAKES
  • Confusing number of blocks with data moved
  • Assuming hardware support reduces complexity
Trap Explanation:
PITFALL
  • Candidates underestimate cost by focusing on block count, ignoring data movement volume.
Interviewer Note:
CONTEXT
  • Tests understanding of compaction's operational cost and complexity.
Master "Internal vs External Fragmentation - Compaction & Buddy System" in Operating Systems

2 interactive learning modes - each teaches the same concept differently

SolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Operating Systems Quizzes
Banker's Algorithm - Safe State & Resource Allocation - Banker's Algorithm - Safe State & Resource Allocation - Quiz 10hard Banker's Algorithm - Safe State & Resource Allocation - Banker's Algorithm - Safe State & Resource Allocation - Quiz 7medium Context Switch - Cost & Causes - Context Switch - Cost & Causes - Quiz 15hard Deadlock - Four Necessary Conditions (Coffman) - Deadlock - Four Necessary Conditions (Coffman) - Quiz 3easy Disk Scheduling - SSTF, SCAN, C-SCAN - Disk Scheduling - SSTF, SCAN, C-SCAN - Quiz 13medium Page Replacement - FIFO, LRU, Optimal Algorithm - Page Replacement - FIFO, LRU, Optimal Algorithm - Quiz 10hard Paging vs Segmentation - Address Translation - Paging vs Segmentation - Address Translation - Quiz 4medium Round Robin Scheduling - Quantum & Turnaround Time - Round Robin Scheduling - Quantum & Turnaround Time - Quiz 7medium Semaphore vs Mutex - When to Use Which - Semaphore vs Mutex - When to Use Which - Quiz 9hard TLB - Translation Lookaside Buffer & Effective Access Time - TLB - Translation Lookaside Buffer & Effective Access Time - Quiz 7medium