Some confusion

When you want to prove that something is O(n)O(n), we want to say that it holds in the worst case. When you want to disapprove that something is O(n)O(n), you just need to find one example where it doesn’t hold.

Remember your first order logic. If the statement is “there exists a tree such that h(T)=O(logn)h(T) = O(\log n), the disapproval of that statement is “there exists no tree such that h(T)=O(logn)h(T) = O(\log n). It is NOT “there exists a tree such that h(T)O(logn)h(T) \neq O(\log n). This is quite critical!!

Worst case analysis

This general paradigm is as such: we have an adversary who wants to find the worst possible input for our algorithm. With input sizes of nn, we denote the worst possible time as T(n)T(n). So for example, in a sorting algorithm a typical worst case would be an inverse sort where everything is sorted but backwards.

We will use T(n)T(n) in asymptotic analysis, which is detailed below.

Asymptotic analysis

The big idea is that we look at how T(n)T(n) behaves for larger and larger nn, which allows us to disregard everything except for the largest term.

The big pro is that it’s simple and can allow us to compare algorithms, but the con is that it may not represent what we want. For example, 10000000n is “better” than n2n^2

Big O

We seek to answer an important question about our algorithm: how does it perform in the worst possible case?

This is where the big O()O() notation comes in.

The informal definition

If T(n)T(n) is the runtime and g(n)g(n) is some simple function, then we say that T(n)=O(g(n))T(n) = O(g(n)) if some constant scaling of g(n)g(n) outruns T(n)T(n) past a certain point.

So for example, we say that T(n)T(n) in the case above would be O(n2)O(n^2)

Now, O(n)O(n) is the upper bound on runtime. Therefore, it only has a lower bound on what it can be, not an upper bound. For example, T(n)=nT(n) = n is O(n)O(n) but also O(n2)O(n^2) and O(n!)O(n!) Another thing to watch out for: if f=O(g)f = O(g), it is not necessarily true that kf=O(kg)k^f = O(k^g), because we disregard summations of lower terms, and summations turn to products in the exponent, which we can’t disregard.

Formal definition

Actually, we have much of the framework down already. T(n)=O(g(n))T(n) = O(g(n)) if

c,n0>0 s.t. nn0,T(n)cg(n)\exists c, n_0 > 0 \text{ s.t. } \forall n \geq n_0, \\T(n) \leq c\cdot g(n)

“There exists some cc such that for all nn larger than some constant n0n_0, the runtime is less than cg(n)c \cdot g(n)

You can chose other values of cc and n0n_0. Generally speaking, the larger the cc, the smaller the n0n_0

Big Omega

While we started with big O notation as the upper bound, we can also talk about a lower bound Ω\Omega such that T(n)T(n) will outrun Ω\Omega past a certain point.

For example, nlog(n)n \log(n) is Ω(3n)\Omega(3n), which is shown graphically below


It’s very similar. T(n)T(n) is Ω(g(n))\Omega(g(n)) if

c,n0>0 s.t. nn0,T(n)cg(n)\exists c, n_0 > 0 \text{ s.t. } \forall n \geq n_0, \\T(n) \geq c\cdot g(n)

It should be obvious, but if f=Ω(g)f = \Omega(g), then g=O(f)g = O(f).

Big Theta

We say that T(n)T(n) is Θ(g(n))\Theta(g(n)) if T(n)T(n) is O(g(n))O(g(n)) and Ω(g(n))\Omega(g(n)).

Now, this doesn’t mean that T(n)=g(n)T(n) = g(n)!!! In fact, n3+3n=Θ(n3n2)n^3 + 3n = \Theta(n^3 - n^2). This is because at lower constants kk, n3+3nk(n3n2)n^3 + 3n \geq k(n^3 - n^2) at sufficiently high nn, while at larger constants, it’s the other way around. Mathematically, it’s because the intersection is a quadratic, and depending on what the kk is, the roots behave differently.

But the general upshot is that only the largest coefficients seem to matter. More on this to come

Solving for c,n0c, n_0

The easiest way is to set of an inequality, like n3+3n2+2cn3n^3 + 3n^2 + 2 \leq cn^3, and then you do some algebra. For example, you might get 1+3n+2n3c1 + \frac{3}{n} + \frac{2}{n^3} \leq c. Then, you assign some arbitrary n=n0n = n_0, and then find a value of cc that satisfies this expression. The key insight is that, algebraically, there are infinitely many solutions so you must assign something arbitrarily and solve for the other one

Tightness of asymptotic relationships

We call a bound asymptotically tight if it’s possible to “touch” the bound. For example, 2n2=O(n2)2n^2 = O(n^2) is asymptotically tight. We define the little oo notation to represent bounds that are not asymptotically tight, like n=O(n2)n = O(n^2). More formally:

c>0;n0>0;0f(n)<cg(n),n>n0\forall c > 0; \exists n_0 >0; 0 \leq f(n) < c g(n), n > n_0

In other words, no matter how flat or steep we transform this bound function gg, it is possible to find a point where ff does not “touch” the bound again. This is typically a stricter restiction, and as nn → \infty, gg and ff become infinitely far apart (which is not guarenteed in asympotitcally tight bounds)

There exists a similar system for ω\omega notation, where it’s the same as above but just flipped.

Asymptotics in equations and inequalities

Let’s just take a moment to put our hand down on the conventions, because this thing can be confusing. For example, we said something like n=O(n2)n = O(n^2). But what does this even mean? Well, this O(n2)O(n^2) can be thought of as a set, and this equals sign is a membership: nO(n2)n \in O(n^2).

However, in an equation, it’s more of a shorthand anonymous function. For example, 2n2+3n+1=2n2+Θ(n)2n^2 + 3n + 1 = 2n^2 + \Theta(n), where we collapsed down the nn term and all its lessers. We can also understand it as 2n2+3n+1=2n2+f(n)2n^2 + 3n + 1 = 2n^2 + f(n), where fΘ(n)f \in \Theta(n).

For equations like 2n2+Θ(n)=Θ(n2)2n^2 + \Theta(n) = \Theta(n^2), we say that there is some way of making two functions of order n and n^2 such that this equation is satisfied.

A great diagram

And a good intuition

Proof techniques

The simple

To prove that something is of a certain OO or Ω\Omega, it’s an existence proof. Just find the cc and the n0n_0. And this is what a formal proof should look like. Instead of saying something like “the log grows slower than the nn,” find these two values and it will be true.

To prove that something is not a certain O()O(), we can use a proof by contradiction. Start by assuming that there exists some c,n0c, n_0 and then show that it’s impossible

Important: for it to be valid, this cc can NOT depend on the value of nn. In other words, if the validity of the inequality depends on cc “chasing” the nn, then the inequality is the wrong way. Otherwise, you might argue that n2cnn^2 \leq c \cdot n, because the cc could “chase” the nn and then it would become n2n^2. That, obviously, is not legal.

Important note

Because this is an existence proof, you need to specify values of n0,cn_0, c directly. Then, you can move around the nn until you get a bound for nn, and this should check out with what you defined n0n_0 to be. You shouldn’t start by solving for nn and then determining what c,n0c, n_0 should be. This step can be done first, but then you erase these steps and write a new proof that assumes you have the information at the beginning.

The abstract

Here’s the key that may be confusing. You don’t need to solve for actual values! This is expecially relevant if one of your functions had an anonymous function involved, like f=2n2+O(n)f = 2n^2 + O(n).

How would you go about proving that f=O(n3)f = O(n^3)? Well, we use the facts

  1. cnO(n)cn \leq O(n) (definition)
  1. f(n)2n2+cnf(n) \leq 2n^2 + cn (moving into equation)
  1. f(n)2n2+cn2=n2(2+c)f(n) \leq 2n^2 + cn^2 = n^2(2 + c)
  1. And let’s use c=2+cc’ = 2 + c
  1. f(n)cn2cn3f(n) \leq c’n^2 \leq c’n^3, which is what we wanted to show

Do you see how we used this single inequality and propagated it through?

Logical fallacy

When we go to prove complexity, we often require induction. You must pick the constants BEFORE you do the induction. In other words, this is incorrect as the inductive hypothesis: (if we’re proving O(n)O(n))

For every nn, there exists a cc such that T(n)cnT(n) \leq cn

This is because you can easily define a cc for every nn!! Just make it as large as you want at each time step. The key point is that you should be picking cc FIRST. This is what a real inductive hypothesis looks like

There exists a cc such that for every nn, T(n)cnT(n) \leq cn.

Subtle difference but very important!

Side note on induction

Induction proofs can go wrong in a few ways. The classical (and most tricky) way that it gets wrong is during the induction step, it uses an inductive hypothesis that we haven’t assumed yet.

The inductive hypothesis can be wrong WRT the problem, but that’s not a problem of the induction itself. For example, we might use our first example (logical fallacy) and prove something by induction. That proof would be flawless, but the end upshot wouldn’t be.