Algorithm Complexity and Big O Notation - Quiz

Algorithm complexity measures how an algorithm's cost (running time or memory usage) grows as the input size n increases. Big O notation describes this asymptotic behaviour: writing O(f(n)) means the number of operations grows no faster than the function f(n), up to a constant factor. It shows the order of growth rather than exact time, which lets you compare algorithms independently of the machine, language or compiler. For example, O(n) is linear growth (double the data and the time roughly doubles), while O(n^2) is quadratic (double the data and the time grows four times).

From fastest to slowest:

• O(1) — constant: time is independent of input size (accessing an array element by index).
• O(log n) — logarithmic: grows very slowly (binary search).
• O(n) — linear: proportional to the data (a single pass over an array).
• O(n log n) — quasilinear: efficient sorting (merge sort, Arrays.sort).
• O(n^2) — quadratic: nested loops, bubble sort.
• O(2^n) — exponential: brute-force search, naive Fibonacci.

The main rules:

• Constant multipliers are dropped: 8n^4 = O(n^4), (n^2)/5 = O(n^2).
• Only the fastest-growing term counts: n^2 + n = O(n^2), 2^n + n^9 = O(2^n).
• The logarithm base is omitted — logarithms with different bases differ only by a constant factor, so we just write O(log n).
• Sequential blocks add up, nested blocks multiply: two loops in a row give O(n) + O(n) = O(n), while a loop inside a loop gives O(n) × O(n) = O(n^2).

Time complexity measures how the number of operations (and therefore the running time) grows. Space complexity measures how much extra memory the algorithm uses in addition to the input itself. The two do not have to match: an algorithm can run in O(n) time yet need only O(1) extra memory (walking an array while keeping just a counter). Often you trade one for the other: caching results to save time increases memory usage.

The same algorithm can behave differently depending on the input, so three estimates are distinguished:

• Worst case — the upper bound, denoted with Big O; it is usually quoted because it guarantees the algorithm will be no slower than that.
• Average case — typical behaviour on random input (Θ, "Big Theta").
• Best case — the lower bound (Ω, "Big Omega").

Example: linear search finds the element immediately in the best case — O(1) — but scans the whole array in the worst case — O(n). When people say "linear search is O(n)", they mean the worst case.