Ordered categories in Pandas - Time & Space Complexity

Time Complexity: Ordered categories

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to work with ordered categories changes as the data grows.

Specifically, how does sorting or comparing ordered categories scale with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

# Create a categorical column with order
cats = pd.Categorical(["low", "medium", "high", "medium", "low"], 
                      categories=["low", "medium", "high"], ordered=True)

# Create a DataFrame
df = pd.DataFrame({"priority": cats})

# Sort the DataFrame by the ordered category
sorted_df = df.sort_values(by="priority")

This code creates an ordered categorical column and sorts the DataFrame by that column.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the DataFrame rows based on the ordered category column.
• How many times: The sorting algorithm compares elements multiple times, roughly proportional to n log n, where n is the number of rows.

How Execution Grows With Input

As the number of rows increases, the sorting work grows faster than just adding rows.

Input Size (n)	Approx. Operations
10	About 30 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: The number of operations grows faster than the number of rows, roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means that sorting ordered categories takes more time as data grows, but not as fast as checking every pair.

Common Mistake

[X] Wrong: "Sorting ordered categories is just as fast as scanning the data once."

[OK] Correct: Sorting needs multiple comparisons and rearrangements, which take more time than just looking at each item once.

Interview Connect

Understanding how sorting ordered categories scales helps you explain data processing steps clearly and shows you know how data size affects performance.

Self-Check

"What if the categories were unordered? How would sorting by that column affect time complexity?"

Practice

1. What does setting ordered=True do when creating a pandas categorical variable?

easy

A. It converts categories to numeric values automatically.

B. It sorts the categories alphabetically.

C. It defines a natural order for the categories, allowing comparisons.

D. It removes duplicate categories from the list.

Solution

1. Step 1: Understand the role of ordered categories

   Ordered categories allow pandas to know the sequence of categories, so it can compare them meaningfully.

2. Step 2: Effect of ordered=True

   Setting ordered=True tells pandas to treat the categories as having a specific order, enabling operations like greater than or less than.

3. Final Answer:

   It defines a natural order for the categories, allowing comparisons. -> Option C

4. Quick Check:

   ordered=True means categories have order [OK]

Hint: Ordered=True means categories can be compared by order [OK]

Common Mistakes:

• Thinking it sorts categories automatically
• Assuming it converts categories to numbers
• Believing it removes duplicates

2. Which of the following is the correct way to create an ordered categorical variable in pandas with categories 'low', 'medium', 'high' in that order?

easy

A. pd.Categorical(['low', 'medium', 'high'], categories=['low', 'medium', 'high'], ordered=True)

B. pd.Categorical(['low', 'tiny', 'high'], categories=['low', 'medium', 'high'], ordered=True)

C. pd.Categorical(['low', 'medium', 'high'], ordered=True, categories=['low', 'medium', 'high'])

D. pd.Categorical(['low', 'medium', 'high'], ordered=False, categories=['low', 'medium', 'high'])

Solution

1. Step 1: Check parameter order and names

   pd.Categorical takes data first, then categories, then ordered flag as keyword arguments.

2. Step 2: Identify correct syntax

   pd.Categorical(['low', 'medium', 'high'], categories=['low', 'medium', 'high'], ordered=True) correctly passes data, categories list, and ordered=True in correct order and names.

3. Final Answer:

   pd.Categorical(['low', 'medium', 'high'], categories=['low', 'medium', 'high'], ordered=True) -> Option A

4. Quick Check:

   Correct syntax uses categories= and ordered=True [OK]

Hint: Use categories= first, then ordered=True keyword [OK]

Common Mistakes:

• Passing ordered=True before categories
• Using ordered=False for ordered categories
• Not matching categories list with data

3. What will be the output of this code?

import pandas as pd
cats = pd.Categorical(['medium', 'low', 'high'], categories=['low', 'medium', 'high'], ordered=True)
print(cats > 'low')

medium

A. [False, True, True]

B. [False, False, True]

C. [True, True, False]

D. [True, False, True]

Solution

1. Step 1: Understand the categories and order

   Categories are ordered as low < medium < high.

2. Step 2: Compare each element to 'low'

   'medium' > 'low' is True, 'low' > 'low' is False, 'high' > 'low' is True.

3. Final Answer:

   [True, False, True] -> Option D

4. Quick Check:

   medium and high are greater than low [OK]

Hint: Compare each category to 'low' using order [OK]

Common Mistakes:

• Confusing category order
• Assuming string comparison instead of categorical
• Mixing True/False positions

4. The following code raises an error. What is the cause?

import pandas as pd
cats = pd.Categorical(['low', 'medium', 'high'], categories=['low', 'medium'], ordered=True)
print(cats > 'medium')

medium

A. Comparison operator '>' is not supported for categorical data.

B. The categories list is missing 'high', causing invalid comparison.

C. Ordered=True cannot be used with categories parameter.

D. The data list has duplicate values.

Solution

1. Step 1: Check categories vs data

   Data contains 'high' but categories only include 'low' and 'medium'.

2. Step 2: Understand effect on comparison

   'high' is not in categories, so comparison with 'medium' fails causing error.

3. Final Answer:

   The categories list is missing 'high', causing invalid comparison. -> Option B

4. Quick Check:

   Data must match categories exactly [OK]

Hint: Ensure all data values are in categories list [OK]

Common Mistakes:

• Thinking ordered=True disallows categories
• Believing '>' is unsupported for ordered categories
• Ignoring missing categories in list

5. You have a DataFrame with a column 'size' containing values 'small', 'medium', 'large', and 'extra large'. You want to sort the DataFrame by 'size' in the natural order small < medium < large < extra large. Which code correctly achieves this?

hard

A. df['size'] = pd.Categorical(df['size'], categories=['small', 'medium', 'large', 'extra large'], ordered=True)
df.sort_values('size')

B. df['size'] = pd.Categorical(df['size'], ordered=True)
df.sort_values('size')

C. df['size'] = pd.Categorical(df['size'], categories=['extra large', 'large', 'medium', 'small'], ordered=True)
df.sort_values('size')

D. df.sort_values('size') # No need to set categories

Solution

1. Step 1: Define ordered categories with correct order

   Set categories=['small', 'medium', 'large', 'extra large'] with ordered=True to define natural order.

2. Step 2: Sort DataFrame by the ordered categorical column

   Use df.sort_values('size') to sort according to the defined order.

3. Final Answer:

   df['size'] = pd.Categorical(df['size'], categories=['small', 'medium', 'large', 'extra large'], ordered=True) df.sort_values('size') -> Option A

4. Quick Check:

   Set ordered categories then sort [OK]

Hint: Set ordered categories with correct order before sorting [OK]

Common Mistakes:

• Not specifying categories order
• Using wrong category order
• Trying to sort without ordered categories