Complexity and Constraints

Estimate whether a solution will run in time from the input size, using Big-O and the rule of thumb of about 10^8 operations per second.

25 minCF 800–12007 interactive9 problems

What Big-O counts

Time complexity describes how the number of basic steps grows when the input size n grows. Big-O notation, written $O(\cdot)$ , keeps only the fastest-growing term and drops constants. A loop of 3n + 10 steps is $O(n)$ .

Name	Written	Typical source
constant	$O(1)$	a formula, an array lookup
logarithmic	$O(\log n)$	halving the range each step
linear	$O(n)$	one loop
linearithmic	$O(n \log n)$	sorting
quadratic	$O(n^2)$	two nested loops
cubic	$O(n^3)$	three nested loops
exponential	$O(2^n)$	trying every subset

Rules you will use daily:

Sequential loops add; the largest wins. $O(n) + O(n^2) = O(n^2)$ .
Nested loops multiply: $n$ times $n$ is $n^2$ .
Halving or doubling a counter gives $\log n$ . About 30 halvings turn $10^9$ into 1.

Predict the output

What does this print?

int n = 5, cnt = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++) cnt++;
cout << cnt;

Your answer

Predict the output

What does this print?

int cnt = 0;
for (int i = 1; i <= 100; i *= 2) cnt++;
cout << cnt;

Your answer

1 of 8