Big-Oh

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

Example

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

Takeaways

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.

Example

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

Example

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

Answer

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

Example

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

Answer

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

Example

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

Answer

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

Example

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

Answer

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

Example

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?