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.