Real-world modeling in Java - Time & Space Complexity

Time Complexity: Real-world modeling

O(n)

Understanding Time Complexity

When we model real-world things in code, we often create objects and connect them. Understanding how the time to run our code grows helps us write better programs.

We want to know how the program's work changes as we add more objects or details.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import java.util.List;

public class City {
    private List residents;

    public City(List residents) {
        this.residents = residents;
    }

    public void greetAll() {
        for (Person p : residents) {
            p.sayHello();
        }
    }
}
    

This code models a city with many residents and makes each resident say hello once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of residents.
• How many times: Once for each resident in the city.

How Execution Grows With Input

As the number of residents grows, the program says hello to more people, so the work grows too.

Input Size (n)	Approx. Operations
10	10 greetings
100	100 greetings
1000	1000 greetings

Pattern observation: The work grows directly with the number of residents. Double the residents, double the greetings.

Final Time Complexity

Time Complexity: O(n)

This means the time to greet everyone grows in a straight line with the number of residents.

Common Mistake

[X] Wrong: "Adding more residents won't affect how long greetAll takes because it's just one method call."

[OK] Correct: The method loops through every resident, so more residents mean more work and more time.

Interview Connect

Understanding how your code grows with input size shows you can think about efficiency, which is a key skill in real projects and interviews.

Self-Check

"What if greetAll called another method that itself loops through all residents? How would the time complexity change?"