Spaceship operator (<=>) in Ruby - Time & Space Complexity

Time Complexity: Spaceship operator (<=>)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to compare values using the spaceship operator changes as we compare more items.

How does the number of comparisons grow when using <=> in different situations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def compare_all(arr)
  arr.each_cons(2) do |a, b|
    result = a <=> b
    puts "Compare #{a} and #{b}: #{result}"
  end
end

compare_all([3, 1, 4, 1, 5])

This code compares each pair of neighboring elements in an array using the spaceship operator.

Identify Repeating Operations

• Primary operation: Comparing two elements with the <=> operator.
• How many times: Once for each pair of neighbors in the array, which is one less than the number of elements.

How Execution Grows With Input

As the array gets bigger, the number of comparisons grows almost the same as the number of elements.

Input Size (n)	Approx. Operations
10	9 comparisons
100	99 comparisons
1000	999 comparisons

Pattern observation: The number of comparisons grows just a little less than the input size, so it grows in a straight line.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare all pairs grows directly with the number of elements in the array.

Common Mistake

[X] Wrong: "Using the spaceship operator inside a loop makes the time grow faster than the number of elements, like squared."

[OK] Correct: Each comparison only happens once per pair, so the total comparisons grow linearly, not faster.

Interview Connect

Knowing how simple comparisons scale helps you explain sorting and searching tasks clearly, which is a useful skill in many coding situations.

Self-Check

"What if we compared every element with every other element using the spaceship operator? How would the time complexity change?"