Partition assignment in Kafka - Time & Space Complexity

Time Complexity: Partition assignment

O(c * p)

Understanding Time Complexity

When Kafka assigns partitions to consumers, it needs to decide who gets which part of the data.

We want to know how the time it takes to assign partitions changes as the number of consumers and partitions grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simplified partition assignment logic
for (consumer in consumers) {
  assignedPartitions = []
  for (partition in partitions) {
    if (partition belongs to consumer) {
      assignedPartitions.add(partition)
    }
  }
  consumer.assign(assignedPartitions)
}

This code assigns partitions to each consumer by checking all partitions for each consumer.

Identify Repeating Operations

• Primary operation: Nested loops where for each consumer, all partitions are checked.
• How many times: Outer loop runs once per consumer, inner loop runs once per partition.

How Execution Grows With Input

As the number of consumers and partitions grows, the total checks grow by multiplying these two numbers.

Input Size (consumers x partitions)	Approx. Operations
10 x 10	100 checks
100 x 100	10,000 checks
1000 x 1000	1,000,000 checks

Pattern observation: Doubling both consumers and partitions roughly quadruples the work.

Final Time Complexity

Time Complexity: O(c * p)

This means the time to assign partitions grows proportionally to the number of consumers times the number of partitions.

Common Mistake

[X] Wrong: "Partition assignment time depends only on the number of partitions."

[OK] Correct: Because each consumer is checked against all partitions, both counts affect the total time.

Interview Connect

Understanding how partition assignment scales helps you explain system behavior and design efficient data distribution in real projects.

Self-Check

"What if we changed the assignment to only check partitions once and then assign to consumers? How would the time complexity change?"