Method lookup chain in Ruby - Time & Space Complexity

Time Complexity: Method lookup chain

O(n)

Understanding Time Complexity

When Ruby runs a method, it looks through a chain of places to find it.

We want to see how long this search takes as the chain grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module M1
  def greet
    "Hello from M1"
  end
end

class C
  include M1
  def greet
    "Hello from C"
  end
end

obj = C.new
obj.greet

This code calls greet on an object, Ruby looks up the method through the class and included modules.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Ruby checks each place in the method lookup chain one by one.
• How many times: It checks until it finds the method or reaches the end of the chain.

How Execution Grows With Input

As the number of modules and classes in the lookup chain grows, Ruby checks more places.

Input Size (n)	Approx. Operations
3	3 checks
10	10 checks
100	100 checks

Pattern observation: The number of checks grows directly with the chain length.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a method grows in a straight line as the chain gets longer.

Common Mistake

[X] Wrong: "Ruby finds methods instantly no matter how many modules or classes are included."

[OK] Correct: Ruby checks each place one by one, so more places mean more time.

Interview Connect

Understanding method lookup helps you explain how Ruby finds methods and why code organization matters.

Self-Check

"What if Ruby used a cache to remember where methods are found? How would that change the time complexity?"

Practice

1.

What does the method lookup chain in Ruby represent?

easy

A. The list of all variables in a class

B. The order Ruby searches to find a method to execute

C. The sequence of method calls inside a method

D. The order Ruby compiles the code

Solution

1. Step 1: Understand method lookup chain meaning

   The method lookup chain is the path Ruby follows to find a method when called on an object.

2. Step 2: Compare options with definition

   Only The order Ruby searches to find a method to execute correctly describes this as the order Ruby searches for a method to execute.

3. Final Answer:

   The order Ruby searches to find a method to execute -> Option B

4. Quick Check:

   Method lookup chain = method search order [OK]

Hint: Think 'where Ruby looks for methods' [OK]

Common Mistakes:

• Confusing method lookup with variable list
• Thinking it shows method call sequence
• Mixing lookup with code compilation order

2.

Which Ruby code correctly shows the method owner for to_s called on a string?

"hello".method(:to_s).owner

easy

A. String

B. Object

C. BasicObject

D. Kernel

Solution

1. Step 1: Recall where to_s is defined for String

   The to_s method for String objects is actually defined in the Kernel module, which is included in Object, and thus available to String.

2. Step 2: Check method owner for to_s on a String object

   Using "hello".method(:to_s).owner returns Kernel because String does not override to_s.

3. Final Answer:

   Kernel -> Option D

4. Quick Check:

   to_s owner for String = Kernel [OK]

Hint: String inherits to_s from Kernel [OK]

Common Mistakes:

• Assuming method is owned by String
• Confusing Object and BasicObject
• Forgetting Kernel defines to_s

3.

Given this Ruby code, what is the output?

module M1
  def greet; "Hello from M1"; end
end

class C
  include M1
  def greet; "Hello from C"; end
end

obj = C.new
puts obj.greet

medium

A. Hello from C

B. Hello from M1

C. NoMethodError

D. Hello from Object

Solution

1. Step 1: Understand method lookup order with include and override

   Class C includes module M1, but also defines its own greet method, which overrides the module's method.

2. Step 2: Determine which greet method is called

   Ruby looks first in C, finds greet there, so it calls "Hello from C".

3. Final Answer:

   Hello from C -> Option A

4. Quick Check:

   Method override in class wins over included module [OK]

Hint: Class methods override included module methods [OK]

Common Mistakes:

• Thinking included module method runs first
• Expecting NoMethodError due to confusion
• Assuming Object's method is called

4.

What is the error in this Ruby code snippet?

module M
  def hello; "Hi from M"; end
end

class A
  prepend M
  def hello; "Hi from A"; end
end

obj = A.new
puts obj.hello

medium

A. No error, output is "Hi from M"

B. No error, output is "Hi from A"

C. SyntaxError due to prepend usage

D. NoMethodError for hello

Solution

1. Step 1: Understand prepend effect on method lookup

   Prepending module M places it before class A in the lookup chain, so M's methods override A's.

2. Step 2: Determine which hello method runs

   Calling hello on obj calls M's method, outputting "Hi from M".

3. Final Answer:

   No error, output is "Hi from M" -> Option A

4. Quick Check:

   Prepend puts module before class in lookup [OK]

Hint: Prepend modules override class methods [OK]

Common Mistakes:

• Expecting class method to run instead
• Thinking prepend causes syntax error
• Confusing prepend with include

5.

Consider this Ruby code:

module M1
  def info; "M1"; end
end

module M2
  def info; "M2"; end
end

class Base
  def info; "Base"; end
end

class Derived < Base
  include M1
  prepend M2
end

obj = Derived.new
puts obj.info

What will be printed and why?

hard

A. M1, because include puts M1 before Base

B. Base, because class method overrides modules

C. M2, because prepend puts M2 before Derived in lookup

D. NoMethodError, info not found

Solution

1. Step 1: Analyze method lookup order with prepend and include

   Prepend M2 places it before Derived, then Derived, then included M1, then Base.

2. Step 2: Identify which info method is called

   Since M2 is first in lookup, its info method runs, printing "M2".

3. Final Answer:

   M2, because prepend puts M2 before Derived in lookup -> Option C

4. Quick Check:

   Prepend > class > include > superclass [OK]

Hint: Prepend modules come before class, include after [OK]

Common Mistakes:

• Thinking include module method runs first
• Assuming class method overrides prepend module
• Ignoring method lookup chain order