Implementing interfaces in Java - Time & Space Complexity

Time Complexity: Implementing interfaces

O(n)

Understanding Time Complexity

When we implement interfaces in Java, we write methods that follow a contract. It's important to see how the time it takes to run these methods changes as the input grows.

We want to know: how does the running time grow when the input size increases in these implementations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public interface Printer {
    void printAll(String[] messages);
}

public class SimplePrinter implements Printer {
    public void printAll(String[] messages) {
        for (String msg : messages) {
            System.out.println(msg);
        }
    }
}
    

This code defines an interface with a method to print all messages, and a class that implements it by printing each message one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array of messages to print each one.
• How many times: Once for each message in the input array.

How Execution Grows With Input

As the number of messages grows, the time to print them grows too, because each message is handled one by one.

Input Size (n)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: The time grows directly with the number of messages; doubling messages doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the printAll method grows in a straight line with the number of messages.

Common Mistake

[X] Wrong: "Implementing an interface method always takes constant time because it's just one method call."

[OK] Correct: The method can do work that depends on input size, like looping through an array, so time can grow with input.

Interview Connect

Understanding how your interface methods scale with input size shows you can write efficient code and reason about performance, a key skill in real projects.

Self-Check

"What if the printAll method called another method inside the loop that itself loops over the messages? How would the time complexity change?"