Array sorting and reversing in Ruby - Time & Space Complexity

Time Complexity: Array sorting and reversing

O(n log n)

Understanding Time Complexity

When we sort or reverse an array, we want to know how the time it takes changes as the array gets bigger.

We ask: How does the work grow when the array size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

arr = [5, 3, 8, 1, 2]
sorted_arr = arr.sort
reversed_arr = sorted_arr.reverse
puts reversed_arr

This code sorts an array and then reverses the sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the array (arr.sort) which compares and rearranges elements.
• How many times: Sorting usually looks at many pairs of elements multiple times depending on the algorithm.
• Secondary operation: Reversing the array (arr.reverse) which swaps elements from start to end once.
• How many times: Reversing goes through the array once, swapping pairs.

How Execution Grows With Input

Sorting takes more time as the array grows, much more than just going through it once.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons and swaps
100	About 700 to 1000 comparisons and swaps
1000	About 10,000 to 15,000 comparisons and swaps

Pattern observation: Sorting grows faster than the size itself, roughly like n times log n. Reversing grows just like the size.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the array grows, but reversing only adds a small extra step.

Common Mistake

[X] Wrong: "Sorting and reversing both take the same time because they both touch every element."

[OK] Correct: Reversing just swaps elements once, so it grows linearly. Sorting compares many pairs multiple times, so it grows faster than just the number of elements.

Interview Connect

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

Self-Check

"What if we used a different sorting method that is already optimized for nearly sorted arrays? How would the time complexity change?"