1.4 Frequency Count Method

knowledge is frequency count met her will did some algorithms and find out how this method is useful for five to ten complexity of algorithms this algorithm is for finding sum of all the elements in an ie here is an array assume that there's an ally of so many means I'm a piggelin array of size five with some elements in it so what is n + 5 so it is this array and NS 5 what this algorithm is to me it is finding is a form of all the elements in an array let us analyze the time taken by the cell column so how do we do that by using frequency count method so the time taken by an algorithm can be known by assigning one unit of time for each statement and if any statement is repeating for some number of times the frequency of statement the frequency of execution of that statement will calculate and we find that time taken by that Alberto so here we have some statement this is a statement which is repeating for some number of times so we will find out its frequency and that will give us the time taken by the cell kata so let us see so this is a simple statement so this takes one unit of time and as the C language code follow by habit on this a C language for in this one we know of the still execute for one time and this will repeat for any time but this condition will be checked for n plus 1 time how when n is 5 the first time I go zero is less than and when I is the one one is less than n I used to tool is less than n is a 3/3 those who lived an N for those who less than fighters not less than n so it will stop so I was initially already zero so how many times I has changed fight ends then how many times condition is checked one two three four five six times five plus one four times it was true and fair time it was false when it became five it was false so it has stopped so this is executing 400 us one times so you say that if you sum up this this is 2 n plus 2 but we write n plus 1 so it means we are bothered about this phenomena right we have whatever only this one we don't want to write about those things usually it is written n plus 1 only but if you observe it carefully it is true L plus true but we don't want to write the time taken by these two right as I said we'll be doing it briefly then whatever the statement is there inside this room I ask this is repeating for n times this is statement alone so we paid for at times so this is n times so now we can understand that whatever is written in the loop like this type of loop the statement legible for n times and the loop itself if you take it will execute for n plus 1 times then the last statement it will make you for one time then what's the time function f of n is 2 n plus 1 2 3 that's it this is the time function now what is the degree of that polynomial it is a degree one it is just n so we say order off and I am calling it as order of I am NOT saying big or theta we will learn it in some other video now for now I will say order of n this complexity see what are the variables used here it is used and s and the size of is and words and all these are just one one word so total is how much n plus 3 so that space complexity is s of NS n plus 3 now this polynomial is also degree n so we say Otto space complexity we got it as order of N and the time complexity is also order now Nextel governments for finding the sum of two matrices a and B are square matrices of dimension n cross n cross n for example it is 3 cross 3 then these mattresses or two-dimensional arrays of size 3 by 3 dimensions are 3 where we assume that so n by n there and wagon now here I have an algorithm for finding the sum of two matrices let us find out the time complexity for this one for them already you know this will take n plus 1 time now whatever is there inside this loop will is u4 n times this is and this is all and two legs are two statements are they each is taking and then what is this again the Zulu so focus also and blessed one then the game whatever is there inside this one will execute for ten times that's it nor is the time taken by this one F of n is and square and square 2 m squared plus and this is the time function for this what is the degree highest degree 2 so we don't write degree V night and square or rough and square so we are writing the degree we are not saying that it is equal to this one we are saying that degree of this polynomial is n square that's all this is the time complexity little state space complexity what are the variables that is having a we see the B and C I and I J what are ABC they are matrices two dimensional arrays and cross n and square and square and square what are an i J they are scalar variables simple variables one word one word one word so space function is 3 and square plus 3 then what is the degree and square so this also and square space complexity is also N squared so the time and the space complexity of this algorithm is N squared how to find the time complexity I have shown it here how to find the space complexity I have shown it here so for few algorithms I'm going to be showing for any other algorithm you can find out this one by following this approach next algorithm is multiplication of two matrices you can see that there are three loops nested one inside another one inside another let us find out the time on this side I would write this would be little far away so this side is right so you can see them this is n plus 1 whatever is there inside will execute for and dimes every statement and times then again this a loop so this is n plus 1 whatever is there inside it will execute for n times so into n into n 2 then again this loop so this is n plus 1 times whatever is there inside will execute for n times again so as the statement is inside all 3 loops so this is going to execute 4nq times this is inside just these two lose these two so this is executing for n square and these are mu step so that's n plus 1 and this is n square and thank you if you finally write down the time function f of n will be equals to C thank you and one more and q2 and u plus this is the N squared and this is M square and this one wooden square so three n square plus this is one n + 2 n so 2 n plus 1 that's it now you've got the degree of the polynomial as Q so the time function is order off and you order of n cube policy space for this one space complexity for this one video sorry a B and C is a b and c and i j k and i'm g + k this is a matrix so n square and square and square and all these are 1 1 1 so this is spaces 3 and squared plus 4 so this is order of n square time is order of n cube spaces or rough n square you can have a look at this working so that's it so I have shown you three different algorithms taking different amount of time one was water of N and N squared and n cube next video you can watch the different type of algorithms and also the method how to analyze them

Channel: Abdul Bari

Views: 498,319

Rating: 4.9554567 out of 5

Keywords: Frequency count methods, algorithm analysis, algorithm, analysis, algorithms

Id: 1U3Uwct45IY

Length: 12min 21sec (741 seconds)

Published: Thu Jan 18 2018