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

Practice

1. What is runtime polymorphism in Java?

easy

A. Creating multiple objects of the same class

B. Using multiple classes with the same name

C. Choosing which method to call during program execution based on object type

D. Writing methods with different names in the same class

Solution

1. Step 1: Understand polymorphism concept

   Polymorphism means many forms; in Java, it allows methods to behave differently based on object type.

2. Step 2: Identify runtime polymorphism

   Runtime polymorphism happens when the program decides which overridden method to call during execution, not before.

3. Final Answer:

   Choosing which method to call during program execution based on object type -> Option C

4. Quick Check:

   Runtime polymorphism = method choice at runtime [OK]

Hint: Runtime polymorphism means method choice happens while running [OK]

Common Mistakes:

• Confusing compile-time and runtime polymorphism
• Thinking it means multiple classes with same name
• Believing it is about method overloading

2. Which syntax correctly shows method overriding for runtime polymorphism in Java?

easy

A. class Parent { void show() {} } class Child extends Parent { void show() {} }

B. class Parent { void show() {} } class Child extends Parent { void display() {} }

C. class Parent { void show() {} } class Child { void show() {} }

D. class Parent { void show() {} } class Child extends Parent { void show(int x) {} }

Solution

1. Step 1: Check method overriding rules

   Method overriding requires same method name and parameters in subclass extending superclass.

2. Step 2: Match options with overriding

   class Parent { void show() {} } class Child extends Parent { void show() {} } shows subclass overriding show() method correctly; others differ in method name or parameters.

3. Final Answer:

   class Parent { void show() {} } class Child extends Parent { void show() {} } -> Option A

4. Quick Check:

   Same method name and parameters in subclass = overriding [OK]

Hint: Overriding needs same method name and parameters in subclass [OK]

Common Mistakes:

• Changing method name in subclass instead of overriding
• Changing method parameters (overloading, not overriding)
• Not extending the parent class

3. What is the output of this code?

class Animal {
  void sound() { System.out.println("Animal sound"); }
}
class Dog extends Animal {
  void sound() { System.out.println("Bark"); }
}
public class Test {
  public static void main(String[] args) {
    Animal a = new Dog();
    a.sound();
  }
}

medium

A. Bark

B. Animal sound

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand object and reference types

   Reference is of type Animal, but object is Dog, so overridden method in Dog is called.

2. Step 2: Identify method called at runtime

   Due to runtime polymorphism, sound() of Dog runs, printing "Bark".

3. Final Answer:

   Bark -> Option A

4. Quick Check:

   Overridden method runs based on object type [OK]

Hint: Method called depends on object type, not reference type [OK]

Common Mistakes:

• Thinking reference type decides method called
• Expecting superclass method output
• Confusing compile-time and runtime behavior

4. Find the error in this code related to runtime polymorphism:

class Parent {
  void show() { System.out.println("Parent"); }
}
class Child extends Parent {
  void show(int x) { System.out.println("Child " + x); }
}
public class Test {
  public static void main(String[] args) {
    Parent p = new Child();
    p.show();
  }
}

medium

A. Parent class method show() is private

B. Child class does not override show() method correctly

C. Cannot assign Child object to Parent reference

D. Missing main method

Solution

1. Step 1: Check method overriding in Child class

   Child defines show(int x), which is overloading, not overriding show().

2. Step 2: Understand method call on Parent reference

   Parent reference calls show() with no arguments, but Child has no overriding method, so Parent's method runs.

3. Final Answer:

   Child class does not override show() method correctly -> Option B

4. Quick Check:

   Overriding needs exact method signature match [OK]

Hint: Overriding needs same method signature, not just same name [OK]

Common Mistakes:

• Thinking overloading is overriding
• Expecting Child's show(int) to override show()
• Ignoring method parameters in overriding

5. Given these classes:

class Vehicle {
  void start() { System.out.println("Vehicle starts"); }
}
class Car extends Vehicle {
  void start() { System.out.println("Car starts"); }
}
class Bike extends Vehicle {
  void start() { System.out.println("Bike starts"); }
}
public class Test {
  public static void main(String[] args) {
    Vehicle[] vehicles = {new Car(), new Bike(), new Vehicle()};
    for (Vehicle v : vehicles) {
      v.start();
    }
  }
}

What is the output when this program runs?

hard

A. Vehicle starts
Vehicle starts
Vehicle starts

B. Compilation error due to array initialization

C. Car starts
Vehicle starts
Bike starts

D. Car starts
Bike starts
Vehicle starts

Solution

1. Step 1: Analyze array elements and their types

   Array holds objects: Car, Bike, Vehicle, all as Vehicle references.

2. Step 2: Understand method calls in loop

   Each start() call runs overridden method of actual object type due to runtime polymorphism.

3. Step 3: Determine output lines

   Car prints "Car starts", Bike prints "Bike starts", Vehicle prints "Vehicle starts" in order.

4. Final Answer:

   Car starts Bike starts Vehicle starts -> Option D

5. Quick Check:

   Overridden methods run per object type in array [OK]

Hint: Loop calls overridden methods based on actual object type [OK]

Common Mistakes:

• Expecting all calls to run Vehicle's method
• Confusing array reference type with object type
• Thinking array initialization causes error