# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

# Notation

Big O notation looks like a math function: $\mathcal{O}(1)$

The contents of the brackets represents the performace. Variables may be used. Generally, the variable $N$ is used, however, more variables may be needed and some may be defined in a problem given. It is convention to use a single letter as a variable. We prefer uppercase ones.

Big O describes the worst-case scenario or at least a plausible worst-case. This makes it easier to quantify the complexity.

Another rule is that only the dominating factors are used. This means that coefficients and lower order terms are discarded.

\mathcal{O}(2N^2+6N) \to \mathcal{O}(N^2)

# Determining Complexity

Complexity is determined by analyzing the number of operations an algorithm performs or the amount of memory allocated by a data structure. For example, if a program looks like the following, then the complexity is $\mathcal{O}(N)$

Similarly, the following is $\mathcal{O}(NM)$

$\mathcal{O}(1)$ is something such as doing an addition operation, accessing a variable, etc.

Logarithmic complexity ($\mathcal{O}(\log N)$) typically comes from some kind of binary search.

# Common Complexities

We will now compare many common complexities. The upper bound on both axes is 100.

Now this is the same graph except on a bigger scale. The upper bound on both axes is 10000.

However, there are a couple of complexities that aren’t didn’t include here because they grow too quickly to be graphed. We will look at them on a logarithmic scale. The upper bound on both axes is 100.

# Constraints

Knowing the maximum constraint of an algorithm is a useful in figuring out the time complexity required to solve a given problem.

In the following is a table, the first row contains the maximum values $N$ that a given complexity can handle with the assumption that the computer can handle ${10\,000\,000}$ operations per second and that you only have a second of run time. The second row contains the number of operations given $N=100$. Actual benchmarks may differ depending on the system. The table is an approximation.

Complexity Maximum Value Operations ($N=100$) Examples
$\mathcal{O}(1)$ N/A $1$ Accessing memory, doing simple math, etc.
$\mathcal{O}(\log N)$ $10^{3\,000\,000}$ $7$ Performing a binary search, using a map or set (both binary search trees).
$\mathcal{O}(\sqrt{N})$ $10^{14}$ $10$ Checking a prime number or prime factorization.
$\mathcal{O}(N)$ $10^{7}$ $100$ An iterative search, a for loop, an iteration, etc.
$\mathcal{O}(N\log N)$ $1\,600\,000$ $665$ Sorting. Using a map or set on $N$ elements.
$\mathcal{O}(N^2)$ $3\,000$ $10\,000$ Most naive sorting algorithms, and absolute worst-case of good ones.
$\mathcal{O}(N^2\log N)$ $1\,700$ $66\,439$ Rarely encountered, no useful examples.
$\mathcal{O}(N^3)$ $200$ $1\,000\,000$ Three nested for loops. 3D DP.
$\mathcal{O}(N^4)$ $56$ $100\,000\,000$ Four nested for loops. 4D DP.
$\mathcal{O}(2^N)$ $23$ $10^{30}$ Finding subsets, bitmasking, combinations.
$\mathcal{O}(N!)$ $10$ $10^{158}$ Combinatorics (permutations) and brute force.
$\mathcal{O}(N^N)$ $8$ $10^{200}$ Combinatorics (permutations).