Subclass with < operator in Ruby - Time & Space Complexity

Time Complexity: Class with < operator

O(n log n)

Understanding Time Complexity

When we define the < operator in a class, it often compares objects. Understanding how long these comparisons take helps us know how the program grows with more data.

We want to find out how the time needed changes as we compare more objects.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Box
  include Comparable
  attr_reader :volume

  def initialize(volume)
    @volume = volume
  end

  def <(other)
    volume < other.volume
  end
end

boxes = [Box.new(10), Box.new(20), Box.new(15)]
boxes.sort!

This code defines a Box class with a < operator to compare volumes, then sorts an array of boxes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing two Box objects using the < operator during sorting.
• How many times: The sort method compares pairs multiple times, depending on the sorting algorithm.

How Execution Grows With Input

As the number of boxes grows, the number of comparisons grows faster than the number of boxes.

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

Pattern observation: When input size grows, comparisons grow much faster, roughly like n × log n.

Final Time Complexity

Time Complexity: O(n log n)

This means if you double the number of boxes, the number of comparisons roughly doubles (not triples).

Common Mistake

[X] Wrong: "Sorting with a custom < operator always takes linear time because it just compares once per item."

[OK] Correct: Sorting needs many comparisons between pairs, not just one per item, so it takes more time as the list grows.

Interview Connect

Understanding how custom comparison affects sorting time helps you explain performance in real programs. It shows you can think about how your code behaves with more data, a key skill in programming.

Self-Check

"What if the < operator compared multiple attributes instead of just one? How would the time complexity change?"