MultiIndex (hierarchical indexing) in Data Analysis Python - Time & Space Complexity

Time Complexity: MultiIndex (hierarchical indexing)

O(m)

Understanding Time Complexity

We want to understand how the time to work with MultiIndex in pandas grows as the data size increases.

Specifically, how does accessing or slicing data with hierarchical indexes affect speed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

n = 10  # example value
m = 5   # example value

# Create MultiIndex from two lists
index = pd.MultiIndex.from_product([range(n), range(m)], names=['level_1', 'level_2'])

# Create DataFrame with MultiIndex
df = pd.DataFrame({'value': range(n*m)}, index=index)

# Access all rows where level_1 == i
i = 0  # example value
result = df.loc[i]

This code creates a MultiIndex DataFrame and accesses all rows for a fixed first-level index value.

Identify Repeating Operations

• Primary operation: Accessing rows by first-level index in MultiIndex.
• How many times: The operation scans or jumps through the subset of rows matching the first-level key, which is about m rows.

How Execution Grows With Input

When we fix the first-level index and get all matching rows, the time depends on how many rows share that first-level key.

Input Size (n x m)	Approx. Operations
10 x 5	5 (rows for one first-level key)
100 x 50	50
1000 x 100	100

Pattern observation: The time grows linearly with the size of the second-level index (m), not the total size (n*m).

Final Time Complexity

Time Complexity: O(m)

This means accessing all rows for a fixed first-level index takes time proportional to the number of second-level entries under it.

Common Mistake

[X] Wrong: "Accessing data by first-level index in MultiIndex is always O(n*m) because the whole DataFrame is scanned."

[OK] Correct: pandas uses efficient indexing to jump directly to the matching rows, so it only processes the subset for that first-level key, not the entire DataFrame.

Interview Connect

Understanding how hierarchical indexing affects data access speed helps you explain efficient data querying in pandas, a key skill for data analysis roles.

Self-Check

"What if we accessed data by both levels of the MultiIndex at once? How would the time complexity change?"

Practice

1. What is the main purpose of a MultiIndex in pandas?

easy

A. To create plots automatically

B. To label data with multiple levels for better organization

C. To convert data into a list

D. To speed up numerical calculations

Solution

1. Step 1: Understand MultiIndex concept

   MultiIndex allows multiple levels of labels on rows or columns, organizing complex data.

2. Step 2: Compare options

   Only To label data with multiple levels for better organization correctly describes MultiIndex's purpose; others describe unrelated features.

3. Final Answer:

   To label data with multiple levels for better organization -> Option B

4. Quick Check:

   MultiIndex = multiple levels labeling [OK]

Hint: MultiIndex means multiple levels of labels [OK]

Common Mistakes:

• Thinking MultiIndex speeds up calculations
• Confusing MultiIndex with plotting tools
• Believing MultiIndex converts data to lists

2. Which of the following is the correct way to create a MultiIndex from tuples in pandas?

easy

A. pd.MultiIndex.build_tuples([('A', 1), ('B', 2)])

B. pd.MultiIndex.create_tuples([('A', 1), ('B', 2)])

C. pd.MultiIndex.make_tuples([('A', 1), ('B', 2)])

D. pd.MultiIndex.from_tuples([('A', 1), ('B', 2)])

Solution

1. Step 1: Recall pandas MultiIndex creation methods

   The correct method to create MultiIndex from tuples is from_tuples.

2. Step 2: Check method names

   Only pd.MultiIndex.from_tuples([('A', 1), ('B', 2)]) uses the correct method name; others are invalid pandas methods.

3. Final Answer:

   pd.MultiIndex.from_tuples([('A', 1), ('B', 2)]) -> Option D

4. Quick Check:

   Use from_tuples to create MultiIndex from tuples [OK]

Hint: Use from_tuples to create MultiIndex from tuple list [OK]

Common Mistakes:

• Using non-existent methods like create_tuples
• Confusing method names with make_tuples or build_tuples
• Forgetting to import pandas as pd

3. Given the code:

import pandas as pd
index = pd.MultiIndex.from_tuples([('A', 1), ('A', 2), ('B', 1)])
data = pd.Series([10, 20, 30], index=index)
print(data.loc['A'])

What is the output?

medium

A. A 10
A 20
dtype: int64

B. 10
20

C. 1 10
2 20
dtype: int64

D. KeyError

Solution

1. Step 1: Understand MultiIndex and selection

   The MultiIndex has two levels: first level 'A' or 'B', second level numbers. Selecting data.loc['A'] returns all entries where first level is 'A'.

2. Step 2: Check values for 'A'

   Entries with first level 'A' are ('A', 1):10 and ('A', 2):20, so output shows index 1 and 2 with values 10 and 20.

3. Final Answer:

   1 10 2 20 dtype: int64 -> Option C

4. Quick Check:

   data.loc['A'] returns second level index and values [OK]

Hint: Selecting first level returns second level index and values [OK]

Common Mistakes:

• Expecting full tuple index in output
• Getting KeyError by wrong indexing
• Confusing index labels with values

4. What is wrong with this code snippet?

import pandas as pd
index = pd.MultiIndex.from_product([['X', 'Y'], [1, 2]])
data = pd.Series([5, 10, 15], index=index)
print(data)

medium

A. The length of data does not match the MultiIndex length

B. from_product is not a valid MultiIndex method

C. Series cannot have MultiIndex

D. The index should be a list, not MultiIndex

Solution

1. Step 1: Check MultiIndex length

   from_product creates all combinations: 2 (X,Y) * 2 (1,2) = 4 index entries.

2. Step 2: Check data length

   Data has length 3, which does not match 4 index entries, causing a ValueError.

3. Final Answer:

   The length of data does not match the MultiIndex length -> Option A

4. Quick Check:

   Data length must match MultiIndex length [OK]

Hint: Data length must equal MultiIndex length [OK]

Common Mistakes:

• Thinking from_product is invalid
• Believing Series can't have MultiIndex
• Assuming index must be list, not MultiIndex

5. You have sales data for two stores over two years stored as a MultiIndex DataFrame with levels ['Store', 'Year']. How do you select sales data for Store 'B' in year 2023?

hard

A. df.loc[('B', 2023)]

B. df['B'][2023]

C. df.loc[2023, 'B']

D. df.loc['B', [2023]]

Solution

1. Step 1: Understand MultiIndex selection syntax

   To select a row with multiple index levels, use a tuple inside loc with all levels specified.

2. Step 2: Analyze options

   df.loc[('B', 2023)] correctly specifies both levels as a tuple. df.loc[2023, 'B'] uses incorrect order of levels (year before store). df['B'][2023] attempts column access first, causing KeyError. df.loc['B', [2023]] uses a list which pandas interprets as column slice, causing KeyError if no such columns.

3. Final Answer:

   df.loc[('B', 2023)] -> Option A

4. Quick Check:

   Use tuple in loc for MultiIndex row selection [OK]

Hint: Use tuple inside loc to select MultiIndex row [OK]

Common Mistakes:

• Reversing the order of index levels
• Using df['B'] to access rows instead of loc with tuple
• Passing list to loc causing column slice misinterpretation