Asymptotic Analysis Part 3: Growth Rates & Time Complexity

let's consider part three of basics of asymptotic analysis from the last lecture we have learned that examining

the exact running time is not the best solution to calculate the time complexity that's what we have learned

from the last lecture right it is not a best practice to know the exact running time of an algorithm so what is the best

solution to this problem there are certain points we need to note here measuring the actual running time is not

at all practical we have learned this already that measuring the actual running time is not at all practical the

running time generally depends on the size of the input I want you to note this point that running time generally

depends on the size of the input now why I'm saying this let's see this with the help of an example suppose we

have an array which consists of three elements like this now what I want to do I want to add one more element to the

beginning of the list let's say this is the element I want to add at the beginning of the list for this purpose

obviously I must have an empty slot here and I need to make three shifts let us assume that if one shift takes one unit

of time then three shifts will take three units of time isn't that so if one shift take one units of time then three

shifts will take three units of time I need to shift each element towards right in order to make an empty slot here now

you can understand that with the size equal to three the time will also be three units after shifting this will

become empty and then I can add the element in the beginning of the list there is no problem in adding this

element right but what if we have 10,000 elements in an array isn't that going to be very tedious because shifting is

costly right adding the element to the beginning of the list is not costly shifting is costly in that case we have

to make 10,000 shifts which will take 10,000 units of time because we have assumed that one shift will take one

unit of time we have to make 10,000 shifts therefore it will take 10,000 two units of time so it is clear from this

fact that running time generally depends on the size of the input here in this case it depends on the size of the array

size of the input or size of the array one and the same thing so if the size of the array is three it takes three units

of time if the size of the array is 10,000 it will take 10,000 units of time the one thing we should note here is

that it totally depends on the size of the input that what is going to be the running

time obviously we are not considering the Machine time that how much time a particular operation will take in a

particular machine we are considering only the size of the input so running time generally depends on the size of

the input this fact we should always remember therefore if the size of the input is n then FN is a function of n

denotes the time complexity so FN is nothing but a function which loads the time complexity it depends on input n ok

or in other words I can say FN represents the number of instructions executed for the input value n let's

consider an example to understand in this statement here in this example I have a printf function within this loop

which runs from 0 to n minus 1 let's say this instruction will take one unit of time this is my assumption let's say

this particular instruction takes one unit of time then we are executing this instruction n number of times so this is

clear that FN will be equal to n because each instruction is taking one unit of time and we are executing this

instruction n number of times right we are executing this instruction n number of times that is why it depends on the

size of the input n and FN will be equal to n because FM is keeping the count of the number of instructions executed for

the input value n this will give us the time complexity but how to find F n you know finding FN in small programs is

easy but as programs become more complex finding FN is not that easy we can compare two data structures for a

particular operation by comparing their FN values we can compare their FN values and then we can compare two data

structures we are interested in growth rate of FM this is very important we are interested in growth rate of FN with

respect to n because it might be possible that for smaller input size one data structure may seem better than the

other but for larger input size it may not this is very important we are interested in growth rate of F and we

have to try different values of N and then we have to find what is going to be the F in value so for different values

of n we should calculate not for just one value of n because it might be possible that one data structure may

better for smaller input size than the other data structure this concept is applicable in comparing the two

algorithms as well it is like you know we can compare two algorithms in the same way we can compare two data

structures in the same way we are interested in growth rate of FN now how to know the growth rate of FN let's

consider one example let's say we have FN equal to five n square plus six n plus twelve this represents time or

number of instructions executed that depends on the input value n of course let's say initially we take n equal to 1

then percentage of running time due to 5 n square will be 5 divided by 5 plus 6 plus 12 we just have to put 1 here this

becomes 5 this becomes 6 this is already 12 so 5 plus 6 plus 12 we will divide 5 by 5 plus 6 plus 12 and then we will

multiply it by 100 in order to calculate the percentage this will give us 20 1.7 for version so we can clearly say that

percentage of running time due to 5 n square is 21 point seven four percent five in square is contributing this much

amount of time obviously this we are calculating for n equal to one let's see what is the

percentage of running time due to 6 n it is 6 divided by 5 plus 6 plus 12 in 200 which is twenty six point zero nine

percent so 6 n is contributing higher than five and square right now let's see what is the percentage of running 9212

it is 12 divided by 5 plus 6 plus 12 into hundred which is 52 point one seven percent it seems like most of the time

is consumed here but wait we have to see the growth rate we cannot say right now that maximum amount of time is taken by

this 12 let's see for the other input values as well let's say n is equal to 10

in that case 5 n square is contributing 87 point 4 1 percent of the running time you can clearly see the growth here from

21 point seven four percent to eighty seven point four one percent while six n is decreasing it decreases from twenty

six point zero nine percent to 10 point four nine percent and 12 which we thought of as taking most of the time is

now taking just two point zero nine percent now let's take n value equal to hundred in that case you can clearly see

the growth 5 n square is contributing the maximum of the time it is 98.7 nine percent while this is just taking 1

point 9% and 12 is just taking 0.02% if you increase the N value further you can

clearly see 5n squared is taking ninety-nine point eight eight percent of the time while 6n is taking 0.12 percent

of the time and 12 is just taking zero point zero zero zero two percent of the time these are almost negligible right

most of the time is consumed here that is in five n square ninety-nine point eight eight percent of the time is

consumed so from this fact it is clear that for larger values of n the squared term consumes almost 99 percent of the

time this term is consuming the most of the time let's say you have taken the value of n equal to one and you simply

say that 12 is taking the most of the time but the reality is different as you are increasing the value of n you can

clearly see which term is taking the most of the time now let's visualize the growth rate here you can clearly see

that squared term is taking most of the time the growth you can see clearly over here while the growth of the constant

term you can also see initially it is high but later it declines faster similar for the

linear term as well you can clearly say that this square term or quadratic term is taking the most of the time right so

there is no harm if we can eliminate the rest of the terms as they are not contributing much to the time we can

eliminate these terms 6n plus 12 we can eliminate them there is no problem in eliminating them because we know that 5

n square term is taking the most of the time it is ninety nine point eight eight percent we are getting the approximate

time complexity is in that so and we are satisfied with this result because this approximate result is very near to the

actual result if we take F n is equal to five and squared there is no harm we know that it is taking ninety nine point

eight eight percent of the time or it may take even more we are getting the approximate time complexity and we are

happy with it there is no problem in eliminating the rest of the terms this concept this

concept of calculating the approximate measure of time complexity is called asymptotic complexity we are not

calculating the exact running time here we are eliminating the unnecessary terms we are only concentrating on the term

which takes most of the time okay so this approximate measure of time complexity is called asymptotic

complexity and this is what we are interested in we are not interested in calculating the exact running time we

are not interested in which machine we are executing our algorithm we are only interested in calculating the

approximate measure of time complexity and we are satisfied with this result we already know this fact that time

complexity depends on the size of the input as you increase the size you can see the time complexity changes so it

depends on the size of the input and we are happy with this result okay friends this is it for now thank you for

watching this presentation [Music] [Applause]

[Music]