Basics of Asymptotic Analysis (Part 5)
My School
This lecture is in the continuation of the previous lecture where we
discussed the big O notation and we have seen some examples related to
big O. Here also, we will see some examples. We will also summarize what
we have learned so far in asymptotic analysis. So, let's get started. Big O
notation is the tool to find the growth rate of the function without plugging
in different values of the size of the input. It gives the least upper bound on
the function, which gives the surety that the function under consideration
will never grow faster than this upper bound. f ( n ) is equal to the big O of
n square, which means that our function grows quadratically. So, we can say
that the growth rate of this function is quadratic. This G (N) is representing
the upper bound on F (n). That is the worst-case time complexity.
We use these standard functions for the least upper bound on a particular
function under consideration. Log n base two has the least growth. While
two. The power N has exponential growth. We usually put them in place on
G ( n ) SO, we can use log n base 2, n square, n cube, n cube, and n square
to get a big O of n square. f ( n) keeps the count of several instructions. We
are interested in finding the growth rate of this function. We can clearly say
that f (n) is equal to big O of n. The growth can be linear only because the
highest term here you can see is n. After that, we have a constant term. The
algorithm written by you for calculating the sum of first n natural numbers
is the fastest among all. Your friend has written. has written an algorithm
that has linear growth. So, your algorithm runs faster than his algorithm.
With Big O notation. We can easily identify which particular program is
better than the other program.
Different programs. One has linear growth and the other one has constant
growth. You can clearly say that. the program written by you is the best and
the program which is written by your friend is not. Okay friends, this is it for
now. Thank you for watching this presentation.
My School
This lecture is in the continuation of the previous lecture where we
discussed the big O notation and we have seen some examples related to
big O. Here also, we will see some examples. We will also summarize what
we have learned so far in asymptotic analysis. So, let's get started. Big O
notation is the tool to find the growth rate of the function without plugging
in different values of the size of the input. It gives the least upper bound on
the function, which gives the surety that the function under consideration
will never grow faster than this upper bound. f ( n ) is equal to the big O of
n square, which means that our function grows quadratically. So, we can say
that the growth rate of this function is quadratic. This G (N) is representing
the upper bound on F (n). That is the worst-case time complexity.
We use these standard functions for the least upper bound on a particular
function under consideration. Log n base two has the least growth. While
two. The power N has exponential growth. We usually put them in place on
G ( n ) SO, we can use log n base 2, n square, n cube, n cube, and n square
to get a big O of n square. f ( n) keeps the count of several instructions. We
are interested in finding the growth rate of this function. We can clearly say
that f (n) is equal to big O of n. The growth can be linear only because the
highest term here you can see is n. After that, we have a constant term. The
algorithm written by you for calculating the sum of first n natural numbers
is the fastest among all. Your friend has written. has written an algorithm
that has linear growth. So, your algorithm runs faster than his algorithm.
With Big O notation. We can easily identify which particular program is
better than the other program.
Different programs. One has linear growth and the other one has constant
growth. You can clearly say that. the program written by you is the best and
the program which is written by your friend is not. Okay friends, this is it for
now. Thank you for watching this presentation.
