🚀 Understanding O(1) vs O(n) – With Practical Code Examples

When writing efficient Java code, algorithmic complexity matters—a lot. In this post, I’ll walk you through two fundamental time complexities: O(1) and O(n), using clear Java 21 examples, and explain which one is more efficient for common search operations.

📌 What Do O(1) and O(n) Mean?

• O(1) – Constant Time: The algorithm takes the same amount of time regardless of input size.
• O(n) – Linear Time: The algorithm’s execution time increases linearly with input size.

🔍 Real Example: Name Search in a Collection

Let’s say you have a list of customer names, and you want to check if a name exists.

👎 O(n) - Linear Search (using List)

import java.util.List;

public class LinearSearchExample {
    public static boolean containsName(List<String> names, String target) {
        for (String name : names) {
            if (name.equals(target)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<String> customerNames = List.of("Alice", "Bob", "Henry", "Diana");
        System.out.println(containsName(customerNames, "Henry")); // true
    }
}

⏱️ Time Complexity: O(n)

🔄 The loop must check each name until it finds the target (or reaches the end).

✅ O(1) - Constant Time Lookup (using Set)

import java.util.Set;

public class ConstantTimeSearchExample {
    public static void main(String[] args) {
        Set<String> customerNames = Set.of("Alice", "Bob", "Henry", "Diana");

        boolean found = customerNames.contains("Henry"); // O(1) lookup
        System.out.println(found); // true
    }
}

⏱️ Time Complexity: O(1) on average

💡 Set uses a hash-based structure (e.g., HashSet) that enables constant-time lookup.

⚖️ Which Is More Efficient?

✅ Verdict: Use Set.contains() if you care about lookup speed—it’s much faster for large collections.

✨ Final Thoughts

Understanding algorithm complexity helps you write scalable, high-performance Java applications.

Knowing when to switch from List to Set can make a massive difference in performance, especially when you're processing thousands (or millions) of items.