In the following series of videos, we'll give a formal treatment of asymptotic
notation, in particular Big-Oh notation, as well as work through a number of
examples. Big-Oh notation concerns functions
defined on the positive integers. We'll call it T of n.
We'll pretty much always have the same semantics for T of n.
We're going to be concerned about the worst case running time of an algorithm
as a function of the input size n. So the question I want to answer for you
in the rest of this video is, what does it mean when we say a function
T of n is Big-Oh of F of n? Where here, F of n is some basic function
like, for example, N log N. So, I'll give you a number of answers.
A number of ways of to think about what Big-Oh notation really means.
But for starters, let's begin with an English definition.
What does it mean for a function to be Big-Oh of F of n?
It means eventually, for all sufficiently large values of n,
it's bounded above by a constant multiple of F of n.
Let's think about it in a couple other ways.
So next, I'm going to translate this English definition into a picture, and
then I'll translate it into formal mathematics.
So pictorially, you can imagine that perhaps we have T of n denoted by this
blue function here. And perhaps, F of n is denoted by this
green function here which lies below T of n.
But when we double F of n, we get a function that eventually crosses T of n
and forever more is larger than it. So in this event, we would say that T of
n indeed is Big-Oh of F of n. The reason being for all sufficiently
large n, once we go out far enough right on this graph, indeed the constant
multiple times F of n, twice F of n N is an upper bound of T of n.
So finally, let me give you actual mathematical definition that you could
use to give formal proofs. So, how do we say in mathematics that
eventually it should be bounded above by a constant multiple of F of n?
We see that there exists two constants, which I'll call c and n0.
So that T of n is no more than c * F(n), for all n that exceed or equal n0.
So the role of these two constants is to quantify what we mean by a constant
multiple and what we mean by sufficiently large, in the English definition.
c obviously quantifies the constant multiple of F of n, and n0 not is
quantifying sufficiently large. That's the threshold beyond which we insist that
c * F(n) is an upper bound on T of n. So, going back to the picture, what are c
and n0? Well, c of course, is just going to be two,
and n0 is the crossing point. So, if you look at where two F of n and T
of n cross, and then we drop the asymptote.
This would be the relevant value of n0 in this picture.
So, that's the formal definition. The way to prove that something's Big-Oh
of F of n, you would exhibit these two constants, c
and n0. And it better be the case that for all n
at least n0, c * F(n) upper bounds, T of n.
One way to think about it if you're trying to establish that something is
Big-Oh of some function, it's like you're playing a game against
some opponent. And you want to prove that this
inequality here holds, and your opponent want to show that it doesn't hold for
sufficiently large n. You have to go. First, your job is to
pick a strategy in a form of a constant c and a constant n0, and your opponent is
then allowed to pick any number n larger then n0.
So the function is Big-Oh of F of n if and only if you have a winning strategy
in this game. If you can upfront commit to constants c
and n0 so that no matter how big an n your opponent picks this inequality
holds. If you have no winning strategy, then
it's not Big-Oh of F of n. No matter what c and n0 you choose your
opponent can always flip this inequality by choosing suitable, suitable large
value of n. I want to emphasize one last thing, which
is that these constants, what do I mean by constant? I mean, they are independent
of n. And so, when you apply this definition
and you choose your constant c and n0, it better be that n does not appear
anywhere. So, c should just be something like 1,000
or a million. Some constant independent of n.
So, those are a bunch of ways to think about Big-Oh notation in English.
You want to have a bound above for sufficiently large numbers n.
I've shown you how to translate that into mathematics, I'd give you a pictorial
representation and also a sort of game theoretic way to think about it.
Now, let's move onto a video that explores a number of examples.