Time complexity describes how an algorithm's work grows as its input grows. Space complexity describes additional storage growth under a stated convention. Big O notation gives an asymptotic upper bound rather than an exact runtime in milliseconds. For Java beginners, counting visits, comparisons, and temporary collections makes these ideas concrete. A linear scan, a nested comparison loop, and a halving search have different growth patterns even if all appear fast on a three-element demonstration.
Choose the input size and operation
State what n means before attaching a complexity label. For an array scan, n is its length and a comparison may be the operation of interest. A program can have two independent sizes, such as rows and columns, requiring O(rows times columns) rather than casually calling everything O(n squared). Input values can also affect early termination. Describe the case being analyzed: best, worst, or an expected average under stated assumptions.
Read constant and linear growth
O(1) work does not grow with the selected input size, such as reading one array element at a known valid index. It does not mean literally one processor instruction. O(n) work grows proportionally, such as visiting every array element once. Two consecutive full scans are still O(n) because constant factors are omitted in asymptotic notation, although those factors can matter in measured performance.
Recognize nested and logarithmic work
Two loops each visiting all n elements commonly perform n times n operations, yielding O(n squared). A loop repeatedly halving a remaining interval needs O(log n) steps. Nested syntax alone is not proof of quadratic growth: if an inner loop always runs three times, the total remains linear. Count the actual iteration bounds and how they depend on input instead of diagnosing complexity from indentation.
Track auxiliary space separately
A scan using a sum variable requires O(1) auxiliary space. Copying n elements into a new array requires O(n). Recursive calls consume stack space, even when no explicit collection is allocated. State whether returned output is included in the space calculation. An algorithm may use constant auxiliary workspace while returning n items, so these conventions affect how you explain its storage needs.
Compare worst-case and average guarantees
A HashMap lookup has expected constant-time behavior under suitable hashing assumptions, not a universal constant-time promise for every adversarial input and operation. Binary search has logarithmic comparisons on sorted random-access data. Reading a file or allocating memory has costs outside a simple comparison count. Use asymptotic analysis to compare growth, then benchmark representative implementations when actual latency and resource use matter.
Preserve correctness before optimizing
Replacing a linear search with binary search only works if the data is sorted under the same comparison rule. Removing validation may reduce counted operations while making the program incorrect. First establish the result contract and meaningful input cases. Then identify the dominant work and possible tradeoffs, such as extra memory for an index. Complexity is a reasoning tool, not a reason to select a clever algorithm whose preconditions the application does not meet.
Practice tasks and checks
Change the arrays and n values so the linear and pair demonstrations run with sizes four and eight. Record eight versus four visits for the scan and sixty-four versus sixteen pairs for the nested loops. Explain the different growth ratios without using stopwatch measurements. Next, make an n-element copy of the input and account for its extra storage separately from the original array. Write a recursive countdown and identify its call-stack growth even though it declares no list. Finally, compare two consecutive linear scans with one nested scan and derive their operation counts. The goal is to explain the dominant term and storage convention, not to memorize a label attached to a particular filename.
Java Summary
- Define input size and the counted operation before stating complexity.
- Nested-loop bounds determine growth, not indentation alone.
- Account for auxiliary storage and recursion stack separately.
- Continue with search algorithm analysis when these examples are clear.
Java Examples
Each example shows the code, the output it produces and what each part does.
Count visits in a linear scan
Save this program as LinearVisits.java. Compile it with javac LinearVisits.java and run it with java LinearVisits.
Expected output:
Each of the four values contributes once to total and once to the visit count. Doubling the array length would double the visits, so the scan has linear time under this operation count. total and visits are a fixed number of variables, giving constant auxiliary space. The array itself is input storage; do not count it as additional workspace allocated by this scan.
public class LinearVisits {
public static void main(String[] args) {
int[] values = {4, 7, 2, 9};
int visits = 0;
int total = 0;
for (int value : values) { total += value; visits++; }
System.out.println(total);
System.out.println(visits);
}
}22
4Count all ordered pairs
Save this program as PairVisits.java. Compile it with javac PairVisits.java and run it with java PairVisits.
Expected output:
The outer loop has four iterations and each runs four inner iterations, producing sixteen ordered index pairs. With an input-dependent n, the count is n squared. The program stores only counters, so its auxiliary space remains constant despite quadratic time. If you changed the inner bound to a fixed three, the count would become three times n and the time classification would become linear.
public class PairVisits {
public static void main(String[] args) {
int n = 4;
int pairs = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) pairs++;
}
System.out.println(pairs);
}
}16Count repeated halving
Save this program as HalvingSteps.java. Compile it with javac HalvingSteps.java and run it with java HalvingSteps.
Expected output:
The successive remaining values are eight, four, two, and one. Four halvings reduce sixteen to one. Increasing the initial size to thirty-two adds only one step rather than doubling the steps, which illustrates logarithmic growth. Integer division rounds downward for positive values, but that does not change the asymptotic classification. This demonstration counts loop work; it does not claim to implement a complete search algorithm.
public class HalvingSteps {
public static void main(String[] args) {
int remaining = 16;
int steps = 0;
while (remaining > 1) { remaining /= 2; steps++; }
System.out.println(steps);
}
}4Java FAQ
Does O(1) always run faster than O(n)?
Not for every small input or implementation. Constants, allocation, and other practical costs matter. Big O describes growth as input scales, not an absolute ranking of all runtimes on one tiny test.
Are two nested loops always quadratic?
No. Their bounds matter. An n-length outer loop with a fixed-size inner loop is linear, while two independent full n-length loops are quadratic. Explain the counted work before naming its class.
Why are constants dropped in Big O notation?
Big O describes how work grows as the input grows, not exact running time. An algorithm doing 2n + 5 steps and one doing n steps both double their work when the input doubles, so both are O(n). Constants still matter in practice, which is why you measure when performance is critical.
What does O(n log n) mean?
The work grows slightly faster than linearly: roughly the input size multiplied by the number of times it can be halved. Efficient general-purpose sorting algorithms such as merge sort take O(n log n). For a million items that's about 20 million steps, compared with a trillion for an O(n²) algorithm.
How do I measure the real speed of Java code?
Timing a single run with System.nanoTime() is misleading, because the JVM compiles and optimises code while it runs. Use a benchmarking harness such as JMH, which warms up the code, repeats runs and reports statistics. Profile whole applications with tools such as Java Flight Recorder.
Java Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What is the auxiliary space of LinearVisits?
How many pairs does PairVisits count when n is 5?
Java Quiz
2 questions to check what you learned.
What growth does repeated halving illustrate?
- O(log n)
- O(n squared)
- O(n factorial)
What must be specified before analyzing complexity?
- Input size and the operation or resource being measured
- Only the class name
- Only whether a loop exists