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