Resource allocation graph in Operating Systems - Time & Space Complexity

Time Complexity: Resource allocation graph

O(V + E)

Understanding Time Complexity

We want to understand how the time to analyze a resource allocation graph changes as the system grows.

Specifically, how does checking for deadlocks scale with more processes and resources?

Scenario Under Consideration

Analyze the time complexity of detecting a cycle in a resource allocation graph.

function detectCycle(graph):
  visited = set()
  recursionStack = set()

  for node in graph.nodes:
    if node not in visited:
      if dfs(node, visited, recursionStack, graph):
        return true
  return false

function dfs(node, visited, recursionStack, graph):
  visited.add(node)
  recursionStack.add(node)
  for neighbor in graph.adjacent(node):
    if neighbor not in visited:
      if dfs(neighbor, visited, recursionStack, graph):
        return true
    elif neighbor in recursionStack:
      return true
  recursionStack.remove(node)
  return false

This code checks if there is a cycle in the graph, which indicates a deadlock.

Identify Repeating Operations

Look for loops and recursive calls that repeat work.

• Primary operation: Depth-first search (DFS) visits each node and its edges.
• How many times: Each node and edge is visited once during DFS.

How Execution Grows With Input

As the number of processes and resources (nodes) and their connections (edges) grow, the time to check for cycles grows roughly in proportion.

Input Size (nodes + edges)	Approx. Operations
10	About 10 to 20 visits
100	About 100 to 200 visits
1000	About 1000 to 2000 visits

Pattern observation: The work grows roughly linearly with the total number of nodes and edges.

Final Time Complexity

Time Complexity: O(V + E)

This means the time to detect deadlocks grows in a straight line with the number of processes and resource connections.

Common Mistake

[X] Wrong: "Checking for deadlocks takes the same time no matter how many processes or resources there are."

[OK] Correct: The more processes and resources you have, the more connections to check, so it takes more time.

Interview Connect

Understanding how cycle detection scales helps you explain system behavior and resource management clearly in interviews.

Self-Check

"What if the graph was represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"