Graphs in social networks in Data Structures Theory - Time & Space Complexity

Time Complexity: Graphs in social networks

O(n + m)

Understanding Time Complexity

When we study graphs in social networks, we want to know how fast we can find friends or connections as the network grows.

We ask: How does the time to explore or search the network change when more people join?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function bfs(graph, start) {
  let queue = [start];
  let visited = new Set([start]);
  while (queue.length > 0) {
    let node = queue.shift();
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}
    

This code performs a breadth-first search (BFS) to visit all connected friends starting from one person.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each person and checking their friends (neighbors).
• How many times: Each person and each friendship connection is checked once.

How Execution Grows With Input

As the number of people (nodes) and friendships (edges) grow, the time to visit everyone grows too.

Input Size (n people, m friendships)	Approx. Operations
10 people, 15 friendships	About 25 checks
100 people, 200 friendships	About 300 checks
1000 people, 3000 friendships	About 4000 checks

Pattern observation: The work grows roughly with the total people plus their friendships combined.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to explore the network grows linearly with the number of people and friendships.

Common Mistake

[X] Wrong: "The BFS will take time proportional to the square of the number of people because everyone might connect to everyone else."

[OK] Correct: In most social networks, not everyone is friends with everyone else, so the number of friendships (edges) is usually much less than the square of people (nodes). BFS time depends on actual connections, not just people count squared.

Interview Connect

Understanding how BFS runs on social networks helps you explain how to find friends or connections efficiently, a skill useful in many real-world problems.

Self-Check

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