How it works
Big-O bounds growth from above, big-Omega from below, and big-Theta applies when both match. Constants and lower-order terms are discarded because they do not affect growth.
Reduce a cost expression to its dominant term, then name the case you are describing.
Common error
Reporting O(3n squared) as if the constant mattered, or conflating worst case with big-O.
Worked example
Java snippets run inside a main method. Add import java.util.*; when collection types are used.
Java
int count = 0;
int n = 4;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) count++;
System.out.println(count);Output
16Two full independent n-iteration loops execute the body n squared times. Asymptotic notation compares growth, so constants and lower-order terms do not change the quadratic classification.
Exercises
2.1.1 · Explain
Compare 3n + 8 with n squared as input size grows.
Show solution
The first is O(n); the second is O(n squared). The quadratic term eventually dominates despite constant factors.
2.1.2 · Explain
A loop repeatedly halves a positive problem size until it reaches 1. What growth class describes its iteration count?
Show solution
O(log n), because each iteration removes a constant fraction of the remaining size.