Complexity and asymptotic analysis

Two programs can both be correct and still differ by a factor of a million once the input gets large. Asymptotic analysis is how we reason about that difference before running anything: it describes how the number of operations grows as the input size grows, stripped of machine speed and constant factors.

Move the input size below and watch the growth curves separate.

The formal definitions #

For functions $f, g : \mathbb{N} \to \mathbb{R}^+$:

• $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$. This is an upper bound.
• $f(n) = \Omega(g(n))$ if $f(n) \ge c\,g(n)$ beyond some point — a lower bound.
• $f(n) = \Theta(g(n))$ if both hold — a tight bound.

The constants $c$ and $n_0$ are exactly what we are allowed to ignore. Big-O says "eventually, no worse than a constant multiple", not "fast for small inputs".

Rules of thumb #

• Drop constants: $3n + 7$ is $O(n)$.
• Keep the dominant term: $n^2 + n \log n + 5$ is $O(n^2)$.
• Sequential code adds, and the sum keeps the larger: a loop then another loop is $O(n) + O(n) = O(n)$.
• Nested code multiplies: an inner loop of $n$ inside an outer loop of $n$ is $O(n^2)$.
• Divide and conquer gives recurrences such as $T(n) = 2T(n/2) + O(n)$, whose solution is $O(n \log n)$.

Which case? #

An algorithm can have different bounds depending on the input:

• Best case — the most favourable input (already sorted).
• Worst case — the input that forces the most work; the usual headline.
• Average case — the expected cost over a distribution of inputs, which requires saying what that distribution is.

Quicksort illustrates why the distinction matters: $O(n \log n)$ on average but $O(n^2)$ on adversarial pivots.

Space complexity is analysed the same way, counting extra memory rather than operations. In-place sorting is $O(1)$ auxiliary space; merge sort is $O(n)$. Amortised analysis spreads a rare expensive operation over the cheap ones around it — the reason appending to a dynamic array is called $O(1)$ despite the occasional reallocation.

Check yourself

Eduspheria wiki · Programming & Data Structures, Algorithms

0 / 5 answered

1. 1Simplify 4n^2 + 3n + 10 to its tight big-O bound.

   A.O(4n^2)B.O(n^2)C.O(n^2 + n)D.O(n)

   Check Show answerMultiple choice
2. 2A loop over n items runs an inner loop over n items. What is the total number of inner-body executions for n = 12?

   executions

   Check Show answerNumeric answer
3. 3Which notation names a tight bound that is both an upper and a lower bound?

   Check Show answerShort answer
4. 4An O(n) algorithm always runs faster than an O(n log n) algorithm.

   TrueFalse

   Check Show answerTrue / false
5. 5How many times does the body of a single loop over n items run for n = 30?

   times

   Check Show answerNumeric answer

From the assignment paper

Modeled on NITJ AI-507, Assignment/Quiz

0 / 5 answered

1. 1What does Big-O notation describe?

   A.the worst-case growth of an algorithmB.the exact running time on a machineC.the average-case growth onlyD.the best-case growth of an algorithm

   Check Show answerMultiple choice
2. 2As n grows large, which of these complexity classes grows fastest?

   A.O(n!)B.O(n^2)C.O(2^n)D.O(n log n)

   Check Show answerMultiple choice
3. 3Which notation states a lower bound, matching an algorithm's best case?

   A.AlphaB.ThetaC.Big-OD.Omega

   Check Show answerMultiple choice
4. 4An algorithm runs in O(n log n). What does that imply about its growth?

   A.it grows faster than linear but slower than quadraticB.it is logarithmic in nC.it is linear on all inputsD.it beats O(n) for small inputs

   Check Show answerMultiple choice
5. 5A routine performs n log2 n basic operations. For an input of size 8, how many operations is that?

   operations

   Check Show answerNumeric answer

Where next: sorting — arranging data in order, and the comparison-based algorithms that do it.