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.
