Runtime polymorphism in Java - Time & Space Complexity

Time Complexity: Runtime polymorphism

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code changes when using runtime polymorphism in Java.

Specifically, we ask: How does choosing methods at runtime affect how long the program runs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Animal {
    void sound() {
        System.out.println("Animal sound");
    }
}

class Dog extends Animal {
    @Override
    void sound() {
        System.out.println("Bark");
    }
}

public class Main {
    public static void main(String[] args) {
        Animal a = new Dog();
        a.sound();
    }
}
    

This code shows a parent class and a child class overriding a method. The method to run is chosen when the program runs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the overridden method sound() on an object.
• How many times: In this example, the method is called once, but in real programs it could be many times.

How Execution Grows With Input

Choosing which method to run happens once per call, so the time grows directly with the number of calls.

Input Size (number of calls)	Approx. Operations
10	10 method lookups and calls
100	100 method lookups and calls
1000	1000 method lookups and calls

Pattern observation: The time increases evenly as the number of calls increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of method calls using runtime polymorphism.

Common Mistake

[X] Wrong: "Runtime polymorphism makes method calls take much longer, so the program slows down a lot."

[OK] Correct: The extra step to decide which method to call is very fast and happens once per call, so it does not cause big slowdowns by itself.

Interview Connect

Understanding how runtime polymorphism affects time helps you explain how programs stay flexible without losing speed. This skill shows you know both design and performance.

Self-Check

"What if we changed the method calls to happen inside a loop running n times? How would the time complexity change?"