Cross-tabulation advanced usage in Pandas - Time & Space Complexity

Time Complexity: Cross-tabulation advanced usage

O(n)

Understanding Time Complexity

We want to understand how the time needed to create a cross-tabulation table changes as the data grows.

Specifically, how does pandas handle counting combinations of categories when the data size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

data = pd.DataFrame({
    'Category1': ['A', 'B', 'A', 'C', 'B', 'A'],
    'Category2': ['X', 'Y', 'X', 'Y', 'X', 'Y'],
    'Values': [1, 2, 3, 4, 5, 6]
})

result = pd.crosstab(index=data['Category1'], columns=data['Category2'], values=data['Values'], aggfunc='sum', dropna=False)

This code creates a cross-tabulation table that sums values for each pair of categories.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: pandas scans each row once to group by category pairs.
• How many times: Once per row, so n times where n is the number of rows.
• Then it aggregates values for each unique category pair, which depends on the number of unique pairs.

How Execution Grows With Input

As the number of rows grows, pandas must process each row once to assign it to a group.

Input Size (n)	Approx. Operations
10	About 10 row scans + grouping
100	About 100 row scans + grouping
1000	About 1000 row scans + grouping

Pattern observation: The work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the cross-tab grows linearly as the number of rows increases.

Common Mistake

[X] Wrong: "Cross-tabulation takes quadratic time because it compares every row to every other row."

[OK] Correct: pandas does not compare rows pairwise; it groups rows by category keys in one pass, so it only needs to look at each row once.

Interview Connect

Understanding how grouping and aggregation scale helps you explain data processing efficiency clearly in interviews.

Self-Check

"What if we added multiple aggregation functions instead of just one? How would the time complexity change?"