YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 269 lines · added Jul 25, 2015

Report a problem
What's wrong?
Advertisement

English transcript

In this lesson we will learn about the concept of asymptotic notations
as a way
to classify the running time of algorithms
into some generic and broad classes
or sets.
In the previous lesson, we had seen
how to calculate the running time
expression
for algorithms using the concept of a hypothetical model machine.
So, Why do we really want to
classify the running time of algorithms into these broad classes.
Let's say we have two algorithms:
Algorithm 1
has the running time defined by this particular function
T (n) = 5n^2 +7 where n is the input size
and Algorithm 2
has the running time defined by 17n^2 + 6n + 8 and let's say we
have deduced these expressions
on a model machine.
We had defined the concept of a model machine in the previous lesson.
A model machine has
some basic operations and
each basic operation like arithmetical, logical or assignment operation
costs us
one unit of time.
Now, these functions
are corresponding to the model machines
but we want some functions or some representation
which is true
irrespective of the machine and still gives us the idea about the rate of growth
of time.
Now couple of things about time complexity analysis:
When we analyze time complexity,
we analyze it
for really really large input sizes, so
we want to analyze
the time taken when n
tends to infinity.
In this case if n tends to infinity
this plus seven in the first function
and this +6 and +8 in the second function will become
insignificant
corresponding (compared) to the n square term
and if n tends to infinity this constant multiplier 5 and 17
also become insignificant
and these two functions will pretty much
have the similar
rate of growth for very high values of n.
So irrespective of the machine
used,
we can say that
these two algorithms have
something like a quadratic rate of growth.
Rate of growth, which is defined by a quadratic function,
which kind of brings these two
functions in the same class.
But we have a very formal way of
classifying
functions into classes,
in the form of asymptotic notations, where
we do not have all these
constants in the expressions
and we only have
the variable term.
And let us now define these asymptotic notations,
and the first asymptotic notation that we want to define is
the Big-oh notation.
If we have a non-negative function
g(n)
that takes
a non-negative argument n
then Big-oh(g(n))
is defined as
the set of all the functions f(n)
for which
there exist
constants...some constants
c and n0
such that
f(n) is less than or equal to
c*g(n)
for all n
greater than or equal to
n0,
and it's the easier to understand this using some example.
Let's say we have a function f(n)
f(n) = 5n^2 + 2n + 1
f(n) = 5n^2 + 2n + 1, and we have
g(n) = n^2
now let's see... this 2n can never be greater than
2n^2
and this 1 can never be greater than n^2, so if we use
c = 5+2+1
c = 5+2+1, which is
8
than f(n)
is always
less than or equal to
8n^2
for all n
greater than or equal to 1.
So for c = 8 and
and n0 = 1,
we can say that f(n) is an element of the set
Big-oh(n^2)
Big-oh(n^2).
and we often also say this as
f(n) = Big-oh(n^2).
And let us now plot these two functions on a graph.
So we have plotted the graph here,
and you can see that
after n = 1,
that is our n0,
c*g(n)
is always greater than f(n).
So this assures that f(n)
never grows at a rate
faster than c*g(n)
after n0.
So in this way,
Big-oh notation kind of, gives us
an upper bound of
the rate of growth of a function,
and in time complexity analysis, this is
very useful because we can say that hey
this is the upper bound of the
rate of growth of time and the...
time can not
grow faster
than this.
Now one more important thing here is that
this c and n0
can be chosen differently so for the same function f(n) and g(n),
we can use,
we can choose different c and n0
and still our
conditions may be valid.
So let us now define another asymptotic notation,
and this notation is called
Omega notation.
And the definition for this notation is that
if we have
a positive function g(n) that takes positive argument n
then Omega(g(n)) is defined as
the set off all the functions f(n)
such that there exist
constant c and n0 for f(n)
so that
c*g(n)
is less than or equal to
f(n)
for all n
greater than
or equal to n0.
Let's pick up an example again
and let's pick up the same example
we had picked up the last time
Let's say our function f(n) is
5n^2 + 2n +1 and our function g(n) is
n^2.
Now, for all n greater than or equal to 0, this
2n+1
will be greater than or equal to 1,
so if we have c = 5 and
n0 = 0,
then clearly
5n^2 is less than or equal to
f(n)
for all n
greater than or equal to 0.
So, we can say that
f(n) is
Omega(n^2)
Omega(n^2).
And let's now plot this on a graph.
What this graph tells us, is that c*g(n) will
never exceed f(n)
for all n
greater than or equal to n0.
So Omega notation gives us
the lower bound of the rate of the growth of a function
and in the context of time complexity analysis
this may be important in the sense that we may say that
that hey
the time taken grows,
at-least by the rate of growth of this particular function g(n).
And let us now see
the third
uh... asymptotic notation.
which is called
Theta notation.
And the definition for this function is that,
if we have a function,
a positive function g(n) that takes positive argument n
then, Theta(g(n))
is defined as
the set of all the functions f(n)
such that
there exist
constants
c1, c2 and n0
for f(n)
such that
c1*g(n)
is less than or equal to
f(n)
which is less than or equal to
c2*g(n)
for all n greater than or equal to n0.
And let's pick up
an example again
and if we pick up the same example that we have picked up
we had picked up earlier for
Big-oh and Omega notation,
f(n) = 5n^2 + 2n +1
and g(n) = n^2
g(n) = n^2.
then, we can choose c1 = 5,
c2 = 8,
and n0
n0 = 1,
and our inequality will hold and we can say that
f(n) is
actually
Theta(n^2)
Theta(n^2).
Now of all the three asymptotic notations, Big-oh, Omega, and Theta that we have
defined
Theta notation best describes
or gives the best idea about the rate of growth of the function
because it gives us
a tight bound
unlike Big-oh and Omega
which give us
upper bound and lower bound.
So, Theta notation kind of tells us that
g(n) is as close to f(n) , the rate of growth of g(n) is as close to
the rate of growth of f(n) as possible.
And let's now plot this on a graph.
so we can see in the graph, that f(n) is bound by these two functions
c1*g(n)
and
c2*g(n)
after n = n0. So this,
f(n) always lies
between
these two .
In time complexity analysis, we should always try to find the
tight bound
expression or the Theta notation
of the time taken
because that gives us the best idea about the time taken
but we also
in a lot of cases use the Big-oh notation
which gives us
an idea about the run time of the algorithm in the worst case.
So these were...
the three
asymptotic notations
that we use for time complexity analysis.
In coming lessons we will
pick up different kind of
algorithms,
different kind of complex algorithms as well like recursion
and see how-to
analyze and deduce these
asymptotic notation expressions for them
So, Thanks for watching !

Need subtitles from another video?