in this video we'll learn about best worst and average case analysis of algorithm so for example I'll be taking two algorithms that is linear search and binary search tree I did two examples linear search and binary search tree so first commonly meanest examples on linear search this is commenting I will take binary search tree also and I'll show you the time case analysis on binary search tree also so you learn about best case and rescues time worst case and worst case time and minimum time interval scales maximum time in worst case and averages so you don't know all these things so and this video you are going to learn these things the first one is linear sub linear search linear search if a set of element list of elements are given then when we are searching for any element in that list then we have different search methods available like linear search and binary search let us see how linear search works here I have a list of n elements and in this I want to search for some key element let us say I want to search for key element 7 what is the method for searching for a key element for looking for a key element the linear search will start scanning the list from left hand side by checking each element at a time so it will start checking whether this is 7 no go to the next element is it 7 no is it 7 is it 7 so it will be go on checking all the elements until either it finds an element yes the element is found so here is an element so totally know how many companies we'll get an element dozen six comparisons we get an element suppose I'm searching for a key element 20 then let us start linear search 20 it will check for the first element no it is not present the next one next one next one next one it will check all the elements and it finds that twenty is not present in the list so when we search in a list the search may be either successful or it may be unsuccessful so far 74 successful and we found it at index five and twenty is not formed when we have checked the entire list so this is our linear search box now let us understand what is best case and what is best is time what's worse case what is worst case time we will find out in this linear search of God first let us see what is best case best case in case if you are searching for a key element which is present at false index then it is the best case in case the case you may be searching for any element from the list but if you are searching for a key element which is present an index first index to the very beginning index then that is best case searching key element present that first index this is best case then what the time it will take if I'm searching for the first key element fear in my example it is the first key element if I'm searching for 8 then it will take constant time best case time is constant I can write it as order of 1 so best case time is 4 n elements this order of 1 this is turning 4 n elements is order of 1 so here I write V of n is 1 now big Omega what is that we will see afterwards so first I have written that function now Volsky is of an algorithm linear search algorithm what's the worst case when the algorithm will take maximum time if I am searching for the key which is at the last index searching a team at last enix in my example 18 is the key we just present at last index so that is the worst case what is the time taken for searching that key element so I have you checked for all the N elements then I can reach there know what is the time taken in this worst case worst case an else and so worst case for enemy menses and and that is water of M so here I write bullski is for n elements is order of n so now I have skills as well as worst-case times given for linear search now average is time average is defined by all possible caves time divided by number of cases so for average case you have to find out all possible cases and the time taken in each possible case and then divided by number of cases so this type of analysis is very difficult on every algorithm so rarely we do it and mostly for average here is the time that we get will be similar to worse case so that's why we prefer finding worst case time for algorithms average case analysis may not be possible always let us check for linear solution what are the cases so let me tell you just in case if you're searching for a key present on first index in case if you're searching for a key present at second index or in case third index in case both index in case and index so these are all cases so in case if you're searching for a key present at first index then average time for this one it is one if I am searching for a key present at second index it will take two comparisons and third index three comparisons and so on last index and comparison total how many come cases are there and cases are there so what is this equal to this is n into n plus 1 by 2 and divided by n this is cancelled and this and plus 1 by 2 so average case time for Emily menses and plus 1 by 2 all these cases and the time complexities we are finding based on number of comparisons how many comparisons are required for finding an element right so my I have best case and it's time and the worst case and it's time at the average case so in average case I consider all possible cases 10 elements are there and possible case assuming researching for first element or second element or third element any element so for each I have taken the time and the number of cases by then so this is n plus 1 by 2 now let us apply asymptotic notations on this phone see I have told you in some video in one video and asymptotic notation that cases are no way related to notation so notations are for the functions cases are the gist of type of analysis done on algorithm let us see how we can apply notations see I have this is time as one can we write this as best case is we go off then we go off one yes I can write we go one can I write it as Omega off one yes can write e times theta of 1 yes see how what is the function function is one constant so when you have a function constant this belongs to constant class so that it directly close to constant class I can use 3 of 1 and even I can use upper bound and lower bound also write this we have already studied asymptotic notation so any function who comes as a perform less than equal to comes out the lower ball an exactly same function it is Theta so this is Theta now whose case the timeless and this belongs to class that is the linear function is linear can I write this as was his time and we go off and yes worse case of NS or Madoff and yes I can write was kiss off and his feet off and yes I can use any of these notations there is no fixed notation to show that this is best here this is worst-case best-case can be written using any notation and the worst case can also be written using any notation right don't take it wrong big voice for worst case or n Omega is for best case no it's wrong you can use it also for best gears or worst case you can use Big O for any cases and even for average is I have a function and us 1 by 2 this blocks which class it belongs to linear class n and so even that I can write it as would be going or theta right so don't mix up in the cases that's already have to do not have proved this one and when you have a function for a function you can use B cos Omega also theta right mostly people confuse that this worst case should be Big O this is upper bound maximum upper bound right lower bomb so Omega no nothing like that you can use any notation now next example is binary search tree here I have a binary search tree I guess I hope that you already know binary search tree the purpose of money search tree is useful for searching the elements are organized such that for every node on the element smaller on the left-hand side all the greater elements on the right-hand side so for searching if you are searching for a smaller element because on this side or greater element we go on website suppose I am searching for 15 let me show you the working if I'm searching for 15 and starts from 20 is it 15 no 15 is a smaller than this one so go to left hand side is it 15 no 15 is greater than this one so on right hand side yes 15 is found so what is the time taken for searching total how many combination I have done only 3 combinations I have done so the time taken is 3 so actually that is equal to the height of at a height of 40 so what is the height we usually call it as log n log n is the height so around 7 7 elements I have bits 8 elements so long 8 is 3 so 3 comparisons are acquired so the height of a tree is log n so the time taken is log n for 15 now let us understand what is best case and what is the best case time was here and was case time the best easiest best cases if I am searching for the element which is present in the root best-case searching root element in short I am writing means I am searching for the key element which is present in the hood so how much time it will take for searching for that particular element this constant at time searching for 20 just check it in the hood yes the element is fun so the best case timeless best-case time yes PN is 1 BN s 1 then what is was his worst case was hisses searching for the element which is presented the leaf searching for leaf element so one of the leaf elements in my example 5 15 35 and 40 if I'm searching and even of those elements than the time will be maximum that is worst case so what is worse it is time worst case time depends on the height of a binary search tree what is the find log in so the worst it is is long and worse is a slow and but now they're not gone there which is now this is a body source tree for the same elements I even I can have a binary search tree like this in the root I have 40 and on the left child I have 30 Ananse left child 25 and on its left child 20 on its left child is 15 and 10 and 5 this is also a binary search tree there's a left skewed binary search tree this is high balanced by Thursday we're using seven elements this is the minimum time that they can have this is the maximum height that can I have now what is the best case in this binary search tree best case is seen for my research the basic is the same searching for that one then what is lower scale is searching for a leaf so we will leave only one element searching for this one is Alaskans but what is the time taken depends on the height of a tree and here also it was dependent on the height of a tree and the height was logon and here the height is and height is 10 so it means that in worse case meaning Mongoose is time as how much login and maximum was his time is how much and so I repeat the point once again at the middle point once again see what's the rules cages for binary search tree searching for an element present in the leaf searching for an element present of the team that is the worst case then what's the most key is a time it depends on the height of her three leaf element will be at the last level so that depends on the height of the tree so what could be the height of a binary search tree the hydrophobicity she can be minimum has login and maximum has Edna so meaning of worst case time maximum worst case time usually this type of questions we find in some competitive exams so worst case means we know it is maximum how it can be minimum so it depends on the type of data structure or type of an algorithm so I have children or worse binary search tree in which we get minimum worst case time as well as maximum skills time so minimum were skills time in slogan magazine University astronomers and because the worst is time depends on the height of a tree I should not write log in here I should write high cover by research th-then wattage that H can be H can be as minimum as logon as maximum as and that's it so these are the best worst-case analysis for a binary search tree now this best case worst case we can write using any notation just like how I have shown in linear search I can use big oh my god data any notation so the things that we studied here is that powers how to find best case and worst case and average is and what notation should be used we got answer for it and sometimes meaning on time inverse is maximum time inverse yes means what that also have explained you this cannot be possible on a real world a more data structure in some situations shitty situations it is possible so this can be raised as a question what would be the minimum time what who the maximum time that's all for this video thank you for watching