Sorting and reversing lists in Python - Time & Space Complexity

Time Complexity: Sorting and reversing lists

O(n log n)

Understanding Time Complexity

When we sort or reverse lists, we want to know how the time needed grows as the list gets bigger.

We ask: How much longer does it take if the list doubles or triples in size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = [5, 3, 8, 1, 2]
my_list.sort()
my_list.reverse()

This code sorts a list in ascending order, then reverses it to get descending order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list, which compares and moves elements multiple times.
• How many times: The sorting process repeats comparisons roughly proportional to n log n of the list size.
• Reversing: Goes through the list once to swap elements from ends to middle.

How Execution Grows With Input

Sorting takes more time as the list grows, but reversing grows more slowly.

Input Size (n)	Approx. Operations
10	About 30 to 50 for sorting, 10 for reversing
100	About 600 to 700 for sorting, 100 for reversing
1000	About 10,000 to 14,000 for sorting, 1,000 for reversing

Pattern observation: Sorting grows much faster than reversing as list size increases.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes longer as the list grows, but not as fast as checking every pair; reversing just goes through the list once.

Common Mistake

[X] Wrong: "Reversing a list takes as long as sorting it."

[OK] Correct: Reversing only swaps elements once each, so it takes much less time than sorting, which compares many pairs.

Interview Connect

Understanding how sorting and reversing scale helps you explain your choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if we used a different sorting method like bubble sort instead of the built-in sort? How would the time complexity change?"