Algorithmic efficiency is imperative for success in programming competitions; your programs must be accurate and fast. To help evaluate algorithms for speed, computer scientists focus on what is called “asymptotics,” or “asymptotic analysis.” The key question answered by asymptotics is: “When your input gets really big, how many steps does your program take?” This post seeks to explain basic asymptotic analysis and its application to computing simple program runtime.

The underlying principle of asymptotic analysis is that a program’s runtime depends on the number of elementary operations it performs. The fewer elementary operations, the faster the program (and vice-versa). What do I mean by “elementary operation?” By this, I refer to any operation such that the runtime is not affected by the input size. This is more commonly referred to as a constant-time operation. Examples of such operations are assignment, basic arithmetic operations (+, -, *, /, %), accessing an array element, increment/decrement operations, function returns, and boolean expressions.

A First Example

So, a good way of gauging the runtime of a program is to count the number of elementary operations it performs. Let’s jump right in by analyzing a simple program.

1public static int test(int N) {
2  int i = 0;
3
4  while(i < N) {
5    i++;
6  }
7  return i;
8}

Obviously, this program always returns $N$, so the loop is unnecessary. However, let’s just analyze the method as-is.

Lines 2 and 7 each contribute one constant-time operation. The loop contributes two constant-time operations per iteration (one for the comparison, one for the increment), plus one extra constant-time operation for the final comparison that terminates the loop. So, the total number of operations is:

$$1 + 1 + \underbrace{\sum_{i = 0}^N 2}_{\text{loop operations}} + 1 = 3 + 2N$$

(Notice how I used sigma (summation) notation for counting a loop’s operation. This is useful, because loops and sigma notation behave in much the same way.)

Thus, it will take $3+2N$ operations to perform that method, given an input $N$. If each operation takes $2\times 10^{-9}$ (about the speed of a 2 GHz processor), it would take 5 seconds to run this program for an input of $N=10^{10}$.