Harold Nelson


Definition of O().

What do we mean when we say that \(f(x)\) is \(O(g(x))\)?

We mean that there exist two constants, \(C\) and \(k\) such that if \(x>k\), then \(f(x)<C*g(x)\).


I assert that \(5x^2+3x+1\) is \(O(x^2)\).

To prove this, note that if \(x>1\), then \(x<x^2\) and \(1<x^2\).

Therefore, when \(x>1\), \(5x^2+3x+1 < 9x^2\).

So, we have our two required constants. \(k=1\) and \(C=9\).


Instead of trying to find the constants for an algorithm, you should focus on what the definition says.

It’s about the shape of the growth of execution time, not the absolute value.

You don’t care about what happens for small sizes of the problem.


Consider the problem of adding up the first n positive integers.

If your process is simply adding up the numbers, that requires n-1 additions, so your algorithm is O(n).

If you know than the sum can be calculated as \[\frac{n(n+1)}{2}\] the algorithm is \(O(1)\).


What is \(O()\) for computing \(N!\)?


This computation requires N-1 multiplications. Therefore it is \(O(N)\).


What is \(O()\) for computing the dot product of two vectors of length N?


This requires N multiplications and N -1 additions. Therefore it is \(O(N)\). You might be tempted to say \(O(2N-1)\).


What is \(O()\) for multiplying an \(M\times N\) matrix with an \(N\times K\)?


This requires the computation of \(M*K\) dot products, each of which requires \(N\) multiplications and \(N-1\) additions.

Therfore the process is \(O(M*K*N)\).


Suppose, in the preceding problem, that the three integers are identical. In other words the two matrices are square.


The process is \(O(M^3)\).


The problem is solving an equation using the half-interval method. You know that a curve crosses the x-axis at a single point between the points \(a\) and \(b\). It is below the axis at \(a\) and above it at \(b\). Your plan is to cut the interval in half as many times as needed to locate the answer to within 1.

Here’s an example.

\[f(x) = x^2-1000\].

Note that \(f(0) = -1000\) and \(f(100) = 9000\).

We know that the curve crosses between \(0\) and \(100\).

The halfway point is \(50\).

\(f(50)\) = \(1500\).

Now we know that the crossing is between \(0\) and \(50\).

Continue this process until you can narrow the location of the crossing down to within an interval of length 1 or less.

What is \(O()\) for this process?


This is process is $O(log(b-a)). Why?