Mastering Java Data Structures and Algorithms
Complexity and Memory
Why We Measure Code
How do you know if a piece of code is 'good'? Is it about the number of lines? Or how fast it runs on your computer? The problem with measuring speed in seconds is that it depends on the machine. A supercomputer will run the same code faster than a laptop. We need a universal way to talk about an algorithm's efficiency, independent of the hardware.
This is where Big O notation comes in. It doesn't measure time in seconds. Instead, it measures how the number of operations an algorithm performs grows as the size of the input grows. It describes the scalability of your code.
Think of it as describing the worst-case scenario. If you're looking for a name in a phone book, the worst case is that the name is the very last one. Big O tells us how that worst-case search time changes if the phone book doubles in size.
| Notation | Name | Common Example |
|---|---|---|
| Constant Time | Accessing an array element by its index. | |
| Logarithmic Time | Finding an item in a sorted array (Binary Search). | |
| Linear Time | Looping through all elements in a list once. | |
| Quadratic Time | Comparing every element in a list to every other element. |
Let's look at a couple of these in code. A simple loop that prints every item in an array is a classic example of linear time, or . If the array has 10 items, it does about 10 operations. If it has 1,000,000 items, it does 1,000,000 operations. The work scales directly with the input size, .
void printAllItems(int[] items) {
for (int item : items) { // This loop runs 'n' times
System.out.println(item);
}
}
Now, consider nested loops. Here, for each item in the array, we loop through the entire array again. This is quadratic time, or . If the array has 10 items, this code performs roughly operations. If it has 1000 items, it performs operations. The number of operations grows much, much faster than the input size. This can become a serious performance bottleneck for large inputs.
void printAllPairs(int[] items) {
for (int firstItem : items) { // Outer loop runs 'n' times
for (int secondItem : items) { // Inner loop runs 'n' times for EACH outer loop iteration
System.out.println(firstItem + ", " + secondItem);
}
}
}
Time vs. Space
Efficiency isn't just about time. It's also about memory. Time complexity describes how many operations an algorithm takes. Space complexity describes how much additional memory the algorithm needs to run.
Sometimes you can improve one at the expense of the other. This is called the time-space trade-off. You might be able to make a function run faster by using more memory to store pre-calculated results (a technique called memoization), or you might save memory by re-calculating values, which takes more time.
Let's analyze the space complexity of a simple function. This function creates a new array that contains the first n integers. The size of this new array is directly proportional to the input n. Therefore, its space complexity is .
// Space complexity: O(n)
int[] createArray(int n) {
int[] newArray = new int[n]; // We allocate memory for 'n' items.
for (int i = 0; i < n; i++) {
newArray[i] = i + 1;
}
return newArray;
}
In contrast, this function just sums the elements of an array. It creates a single new variable, total, to store the sum. Whether the input array has 10 elements or 10 million, we still only need that one extra variable. The memory usage doesn't scale with the input size. This is constant space complexity, or .
// Space complexity: O(1)
int sumArray(int[] items) {
int total = 0; // We only allocate a single integer variable.
for (int item : items) {
total += item;
}
return total;
}
When analyzing complexity, we always drop constants and lower-order terms. An algorithm that runs in is simplified to just , because as gets very large, the
* 2and+ 100become insignificant compared to itself.
How Java Manages Memory
To truly understand space complexity in Java, we need to know how it physically stores data. Java splits memory into two main areas: the Stack and the Heap.
The Stack is a highly organized and fast region of memory. It works on a Last-In, First-Out (LIFO) basis. Each time a method is called, a new 'frame' is pushed onto the stack to hold its local variables. When the method finishes, its frame is popped off. The Stack stores primitive types (int, double, boolean, etc.) and references to objects.
The Heap is a large, less organized pool of memory where all objects are actually created. When you write new MyObject(), the memory for that object is allocated on the Heap. The Heap is slower to access than the Stack but is much larger and more flexible. It's also where Java's automatic Garbage Collector operates, cleaning up objects that are no longer being used.
This distinction leads to a fundamental concept: primitive types vs. reference types.
A variable of a primitive type holds its value directly on the stack. When you write int myAge = 30;, the value 30 is stored in the myAge slot on the stack.
A variable of a reference type doesn't hold the object itself. It holds a memory address—a pointer—that points to where the actual object lives on the Heap.
public void memoryExample() {
// Primitive type: value '42' is stored directly in 'score'
int score = 42;
// Reference type: 'greeting' holds a memory address.
// The actual "Hello, World!" object is on the Heap.
String greeting = new String("Hello, World!");
}
Understanding this is critical. When you pass a primitive variable to a method, you're passing a copy of its value. Changing it inside the method doesn't affect the original.
But when you pass an object reference to a method, you're passing a copy of the address. Both the original reference and the method's parameter now point to the same object on the Heap. If the method uses that reference to change the object, the change is visible everywhere.
Finally, let's consider the different performance scenarios. An algorithm might not always perform the same way.
- Best Case: The most optimal scenario. For a search algorithm, this is finding the item on the first try.
- Average Case: The expected performance over a random distribution of inputs.
- Worst Case: The least optimal scenario, which guarantees a performance upper bound. For a search, this is finding the item last, or not at all.
Big O notation typically focuses on the worst-case scenario because it provides a reliable guarantee. When we say an algorithm is , we're saying it will never be worse than linear time, though it might sometimes be better.
Why is Big O notation a more reliable measure of an algorithm's efficiency than measuring execution time in seconds?
Consider a function that iterates through every cell of a 2D square grid (n x n) to find a value. What is the Big O time complexity of this operation?
Now that you have a framework for analyzing efficiency, we can start exploring specific data structures and see how their design choices impact their time and space complexity.