Choose the input variables
Complexity describes how required resources grow with input size in a defined model. Use n for a list length, m for a second independent list, V/E for graph size, k for a window or capacity, and L for a string length. Big O is an upper bound, Θ a tight asymptotic bound and Ω a lower bound. State the case separately: worst case, expected input behavior and amortized cost are different claims.
Account for the actual operations
Consecutive independent scans add to O(n + m). A full cross-product costs O(nm). A dependent loop such as 1 + 2 + ... + n is quadratic; two advancing pointers may instead perform only linear total steps. Library calls are not free: sorting, copying a slice, hashing a long key, or searching a list can dominate a loop that looks constant at the source-code level.
Count memory honestly
Auxiliary space excludes inputs and often excludes required output, but say which convention you use. Recursion uses stack frames even when no array is allocated. Enumerating all subsets requires exponential output storage if you materialize them. Numeric assumptions also matter: fixed-width arithmetic can overflow, and arbitrary-precision arithmetic costs grow with the number of digits. An asymptotic improvement is useful but does not replace measuring real latency.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
long pairs = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
pairs++;
}
}Walkthrough
The inner counts are n−1, n−2, down to zero. Their sum is n(n−1)/2, which grows quadratically. There are only a few counters, so auxiliary space is constant. Use long for the count and check input constraints; the loop indices and total count have different overflow limits.
Practice it yourself
Analyze a loop that doubles i each time, followed by a scan of all n entries. Then analyze the scan nested inside that doubling loop.
Check your reasoning
The doubling loop has O(log n) iterations for positive n. Consecutive work is O(log n + n) = O(n). Nesting a complete n-element scan in every doubling iteration gives O(n log n). Assume bounded integer arithmetic and prevent overflow in doubling.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.