Next: Sorting techniques. Up: Computational complexity. Previous: None.

Big-O

Definition

Big-O notation is a technique for quickly approximating the speed of a procedure. Basically, it identifies whether the running time grows exponentially with the input size, or whether it grows linearly, or quadratically, or whatever.

We can define the time to run a procedure as T(n), a function T of the input size n. Big-O notation would write something like the following.

T(n) = O(n²) This would say that T(n) grows approximately as quickly as the function f(n) does - that is, that T is bounded by a parabola. (Don't get messed up by the use of O here, which looks mysteriously like a function. The notation ``= O(...)'' is purely syntactic for saying that the function on the left-hand side grows about as quickly as the expression inside the parentheses.)

Formally, the notation T(n) = O(g(n)) means the following: There is some constant c and some input size N, so that for any input sizes n beyond N,

T(n) <= c*g(n)

For example, consider the following code that determines whether a number n is prime.

int i;
for(i = 2; i * i <= n; i++) {
  if(n % i == 0) {
    IO.println("not prime");
    break;
  }
}
if(i * i > n) IO.println("is prime");

This procedure turns out to take O(n^0.5) time: The total number of iterations can be bounded by sqrt(n), and the amount of time for each iteration is bounded by a constant.

Basic rules

There are three helpful rules that you might keep in mind when you're trying to evaluate the speed of a program.

Any segment of code that includes no loops or function calls takes O(1) time.
If one segment of code takes X time and another takes Y time, then doing the first segment followed by the other takes a total of X + Y time.
If each iteration of a loop takes X time and there are Y iterations of the loop, then the overall time for doing the loop is X*Y.

In our primality example, we would reason like the following.

Applying the first rule, we see that the program has the following form.
```
O(1) time
for(...) {
  O(1) time
}
O(1) time
```
Each of the blocks replaced by ``O(1) time'' involved no loops or function calls.
We go through at most sqrt(n) iterations of the for loop, and each iteration takes O(1) time. So (using the third rule above) the total time for the for loop is O(n^0.5). Thus, we can now write the structure of the procedure as follows.
```
O(1) time
O(sqrt(n)) time
O(1) time
```
Employing the second rule, we see that the current form consumes O(1) time, followed by O(sqrt(n)) time, for a total of O(1+sqrt(n)) = O(sqrt(n)). After this, we spend O(1) time again, for a total of O(sqrt(n)+1) = O(sqrt(n) time.

Examples

// exponentation, method 1: finds a to the bth power
ret = 1.0;
for(int i = b; i > 0; i--) ret *= a;
IO.println(ret);

// exponentiation, method 2: finds a to the bth power
ret = 1.0;
int i = n;
while(i > n) {
    if(i % 2 == 0) {
        i = i / 2;
    } else {
        ret *= a;
        i = (i - 1) / 2;
    }
    a = a * a;
}
IO.println(ret);

// count lattice points: determines how many integer-coordinate
//    points lie in a circle of radius r
count = 0;
y = 0;
x = r;
while(x > 0) {
    while(x*x + y*y < r*r) {
        ++y;
    }
    count += y;
}
IO.println(4 * count + 1);

This last example illustrates an example where the ``basic rules'' outlined above give a poor solution: You're better off reasoning through the problem more carefully.

Next: Sorting techniques. Up: Computational complexity. Previous: None.