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.

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)$

for (int n = 0; n < N; n++) {
	// Do something in O(1)
}

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

for (int n = 0; n < N; n++) {
	for(int m = 0; m < M; m++) {
		// Do something in O(1)
	}
}

$\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.