Lambda with sorted() in Python - Time & Space Complexity

Time Complexity: Lambda with sorted()

O(n log n)

Understanding Time Complexity

When we use sorted() with a lambda function, we want to know how the sorting time changes as the list grows.

We ask: How does the work needed to sort change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [(1, 3), (3, 2), (5, 1), (2, 4)]
sorted_numbers = sorted(numbers, key=lambda x: x[1])
print(sorted_numbers)

This code sorts a list of pairs by the second number in each pair using a lambda function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing elements using the lambda key function during sorting.
• How many times: The sorting algorithm compares elements multiple times, depending on the list size.

How Execution Grows With Input

As the list gets bigger, the number of comparisons grows faster than the list size itself.

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

Pattern observation: The work grows faster than the list size, roughly like the list size times its logarithm.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the list grows, but not as fast as checking every pair with every other pair.

Common Mistake

[X] Wrong: "Using a lambda makes sorting slower by a lot because it adds extra work for each comparison."

[OK] Correct: The lambda function runs once per element to compute keys, not once per comparison, so the main time is still spent in sorting steps, and the overall growth stays the same.

Interview Connect

Understanding how sorting with a custom key works helps you explain how your code handles data efficiently, a useful skill in many coding tasks.

Self-Check

"What if we replaced the lambda with a precomputed list of keys? How would the time complexity change?"