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

Practice

1. In Ruby, what does the expression ChildClass < ParentClass check?

easy

A. If ChildClass and ParentClass are the same class

B. If ChildClass is an instance of ParentClass

C. If ChildClass is a subclass of ParentClass

D. If ParentClass is a subclass of ChildClass

Solution

1. Step 1: Understand the < operator for classes

   In Ruby, the < operator between classes checks inheritance, specifically if the left class is a subclass of the right class.

2. Step 2: Apply to ChildClass < ParentClass

   This expression returns true if ChildClass inherits from ParentClass, meaning ChildClass is a subclass.

3. Final Answer:

   If ChildClass is a subclass of ParentClass -> Option C

4. Quick Check:

   Subclass check = true if inheritance [OK]

Hint: Remember: < means 'is subclass of' in Ruby classes [OK]

Common Mistakes:

• Confusing subclass check with instance check
• Thinking < checks equality of classes
• Reversing the order of classes in the expression

2. Which of the following is the correct syntax to check if Dog is a subclass of Animal in Ruby?

easy

A. Dog < Animal

B. Dog.is_subclass_of?(Animal)

C. Dog.subclass_of? Animal

D. Dog < Animal()

Solution

1. Step 1: Recall Ruby subclass syntax

   Ruby uses the < operator between classes to check subclass relationships, like Dog < Animal.

2. Step 2: Evaluate options

   Methods like is_subclass_of? and subclass_of? do not exist on classes. Dog < Animal() has incorrect syntax with parentheses. Only Dog < Animal is valid Ruby syntax.

3. Final Answer:

   Dog < Animal -> Option A

4. Quick Check:

   Correct syntax uses < operator [OK]

Hint: Use < directly between classes, no method needed [OK]

Common Mistakes:

• Using methods that don't exist for subclass check
• Adding parentheses incorrectly
• Using instance methods instead of class operators

3. What is the output of this Ruby code?

class Vehicle; end
class Car < Vehicle; end
class Bike; end

puts Car < Vehicle
puts Bike < Vehicle

medium

A. false
false

B. true
false

C. true
true

D. false
true

Solution

1. Step 1: Analyze class inheritance

   Car inherits from Vehicle, so Car < Vehicle returns true. Bike does not inherit from Vehicle, so Bike < Vehicle returns false.

2. Step 2: Determine output of puts statements

   The first puts prints true, the second prints false, each on its own line.

3. Final Answer:

   true false -> Option B

4. Quick Check:

   Subclass true, unrelated false [OK]

Hint: Subclass < Parent = true; unrelated classes = false [OK]

Common Mistakes:

• Assuming unrelated classes return true
• Confusing instance and class comparisons
• Mixing up order of classes in < operator

4. Consider this Ruby code snippet:

class Fruit; end
class Apple < Fruit; end

puts Apple < fruit

What is the error and how to fix it?

medium

A. No error; output is true

B. SyntaxError: invalid syntax; fix by adding parentheses

C. TypeError: wrong argument type; fix by using instance instead of class

D. NameError: uninitialized constant 'fruit'; fix by capitalizing 'Fruit'

Solution

1. Step 1: Identify the error

   The code uses lowercase 'fruit' instead of 'Fruit'. Ruby constants (classes) must start with uppercase letters. This causes a NameError.

2. Step 2: Fix the error

   Change 'fruit' to 'Fruit' to reference the class correctly.

3. Final Answer:

   NameError: uninitialized constant 'fruit'; fix by capitalizing 'Fruit' -> Option D

4. Quick Check:

   Class names start uppercase [OK]

Hint: Class names always start with uppercase letter [OK]

Common Mistakes:

• Using lowercase for class names
• Confusing variables with class constants
• Trying to call < on instances instead of classes

5. You have these Ruby classes:

class Animal; end
class Mammal < Animal; end
class Dog < Mammal; end
class Fish < Animal; end

puts Dog < Animal
puts Fish < Mammal
puts Mammal < Dog

What is the output and why?

hard

A. true
false
false

B. true
true
false

C. false
false
true

D. true
false
true

Solution

1. Step 1: Evaluate Dog < Animal

   Dog inherits from Mammal, which inherits from Animal, so Dog is a subclass of Animal. Returns true.

2. Step 2: Evaluate Fish < Mammal

   Fish inherits directly from Animal, not Mammal. So Fish is not a subclass of Mammal. Returns false.

3. Step 3: Evaluate Mammal < Dog

   Mammal is a superclass of Dog, not a subclass. So this returns false.

4. Final Answer:

   true false false -> Option A

5. Quick Check:

   Subclass chain true, unrelated or reversed false [OK]

Hint: Subclass < superclass = true; reversed or unrelated = false [OK]

Common Mistakes:

• Assuming superclass < subclass returns true
• Ignoring multi-level inheritance
• Mixing up class hierarchy direction