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?"

Practice

1. What does the key argument do when used with sorted() and a lambda function in Python?

easy

A. It reverses the order of the sorted list automatically.

B. It changes the original list to a sorted list in place.

C. It tells sorted() how to compare items by extracting a value from each item.

D. It filters out items that do not match the lambda condition.

Solution

1. Step 1: Understand the role of key in sorted()

   The key argument takes a function that extracts a value from each item to use for sorting.

2. Step 2: Understand how lambda works with key

   The lambda function defines this extraction rule inline, telling sorted() what to compare.

3. Final Answer:

   It tells sorted() how to compare items by extracting a value from each item. -> Option C

4. Quick Check:

   key=lambda x: value means compare by value [OK]

Hint: Remember: key=lambda extracts sort value from each item [OK]

Common Mistakes:

• Thinking key changes the original list
• Confusing key with reverse sorting
• Assuming lambda filters items

2. Which of the following is the correct syntax to sort a list of tuples data = [(2, 'b'), (1, 'a'), (3, 'c')] by the first element using sorted() and a lambda?

easy

A. sorted(data, key=lambda x: x[0])

B. sorted(data, lambda x: x[0])

C. sorted(data, key=lambda x: x[1])

D. sorted(data, key=x[0])

Solution

1. Step 1: Identify the correct use of key argument

   The key argument must be named and assigned a function, here a lambda.

2. Step 2: Check lambda syntax and index

   lambda x: x[0] correctly extracts the first element of each tuple for sorting.

3. Final Answer:

   sorted(data, key=lambda x: x[0]) -> Option A

4. Quick Check:

   Correct syntax uses key= and lambda with index [OK]

Hint: Always use key= with lambda for sorting rules [OK]

Common Mistakes:

• Omitting key= argument name
• Using wrong tuple index
• Passing lambda as second positional argument

3. What is the output of this code?

data = ['apple', 'banana', 'cherry']
sorted_list = sorted(data, key=lambda x: len(x))
print(sorted_list)

medium

A. ['apple', 'banana', 'cherry']

B. ['banana', 'cherry', 'apple']

C. ['cherry', 'banana', 'apple']

D. ['apple', 'cherry', 'banana']

Solution

1. Step 1: Understand sorting by length

   The lambda extracts the length of each string: apple(5), banana(6), cherry(6).

2. Step 2: Sort strings by their length

   Sorted order by length is: apple(5), banana(6), cherry(6). Since banana and cherry have same length, original order among them is preserved (banana before cherry).

3. Final Answer:

   ['apple', 'banana', 'cherry'] -> Option A

4. Quick Check:

   Sort by len(x) = ['apple', 'banana', 'cherry'] [OK]

Hint: Sort by length with key=lambda x: len(x) [OK]

Common Mistakes:

• Assuming alphabetical sort instead of length
• Mixing order of equal length items
• Forgetting sorted returns new list

4. Find the error in this code snippet:

data = [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}]
sorted_data = sorted(data, key=lambda x: x['age'])
print(sorted_data)

medium

A. The code will raise a KeyError because 'age' is missing.

B. There is no error; the code sorts by age correctly.

C. The lambda function should use double quotes for keys.

D. sorted() cannot sort dictionaries.

Solution

1. Step 1: Check dictionary keys and lambda syntax

   Each dictionary has the key 'age', and lambda accesses it correctly with single quotes.

2. Step 2: Confirm sorted() usage on list of dicts

   sorted() can sort list of dictionaries using key function; no error occurs.

3. Final Answer:

   There is no error; the code sorts by age correctly. -> Option B

4. Quick Check:

   Access dict keys with quotes; sorted works on list of dicts [OK]

Hint: Dictionaries can be sorted by key with lambda [OK]

Common Mistakes:

• Thinking single quotes cause error
• Assuming KeyError without missing keys
• Believing sorted() can't handle dicts

5. You have a list of tuples representing products and their prices:

products = [('pen', 1.5), ('notebook', 2.0), ('eraser', 0.5), ('pencil', 1.5)]

How would you sort this list first by price ascending, then by product name alphabetically using sorted() and lambda?

hard

A. sorted(products, key=lambda x: x[1] and x[0])

B. sorted(products, key=lambda x: x[1] or x[0])

C. sorted(products, key=lambda x: x[0], x[1])

D. sorted(products, key=lambda x: (x[1], x[0]))

Solution

1. Step 1: Understand sorting by multiple criteria

   To sort by price then name, use a tuple in key: (price, name).

2. Step 2: Write lambda returning tuple for sorting

   lambda x: (x[1], x[0]) returns price first, then product name.

3. Final Answer:

   sorted(products, key=lambda x: (x[1], x[0])) -> Option D

4. Quick Check:

   Use tuple in key=lambda for multi-level sort [OK]

Hint: Use tuple in lambda key for multi-level sorting [OK]

Common Mistakes:

• Using logical operators instead of tuple
• Passing multiple key arguments
• Reversing order of sort keys