1.11 Best Worst and Average Case Analysis

Case Analysis Discussed in this video

1. Best
2. Worst
3.Average

Examples Taken

1. Linear Search
2. Binary Search Tree

Min time in Worst Case
Max time in Worst Case
are also discussed.

Courses on Udemy
================
Java Programming

Data Structures using C and C++

C++ Programming

[diwang]

It is ridiculous that I spent 70k+ at College for this and what my teacher has taught makes me confused. While this video makes things so clear, and I have not spend a penny for it! Thank you!

[hondaicg]

I don't know why mostly peoples run toward great institution like algoexpert website, MIT and Howard and paid huge amount of tuition fees.This is the real Algorithm Expert man deserve reward in case of donation to encourage his hard work and passion, honestly no one can teach like this Teacher.

[waqarahmad_cs]

brilliant

The 74 people who disliked are University teachers who are probably jealous.

[maharshpatel]

His content is so good, i did not skip the ad intentionally so that he earns all the money possible for creating such amazing videos

[lorenzozuluaga]

abdul i really appreciate that you share this knowledge for us!, also im finishing ur c++ begginer to advanced course and lend me tell you you are the best teacher i ever seen, when i finish it i will continue with ur mastering data structures and algorithms with c & c++, please never stop building this quality content bless from colombia sir!

[monoswitachatterjee]

I have my Amazon SDE assessment coming up in a day & I am watching your videos on loop sir. Because no one can teach these concepts in the crystal clear way you do. Hope you continue making more videos on teaching the fundamentals in the best and basic way possible. Much love & respect for you sir! :) You're truly one of a kind!

[nithikasiriwardana]

They need to name a tech-university after this man. Learned more from this 18 minute free video than I ever did from my $30k uni course. Thank you so much Sir

[debolinasihi]

Honestly i was scared of algorithm, i was looking for courses, looking for help of my teachers, end of the day i was running from it, whem i was tired of it i even tried to read cormen, but nothing really helped. I know algorithm is a very important subject, and we can't neglect it, so i had to do it. I don't know without you how on earth i would do it, . I'm so thankful to you sir, 🙏🙏 please make more videos, .

[tngaw]

rare to find such simple explanations on youtube. Keep it up Sir.

[sonakshimishra.]

No matter what I write, it will always fall short for the kind of teacher you are. Thank God, I found you sir. So overwhelmed by the simplicity, knowledge, clarity and those pauses! Thank you, for being available for ignorant students like us. 🙏🙏🙏

[fezanbhatti]

Ma Sha Allah ap ka teaching method bohat zabardast hey. I even tried put MIT Open CourseWare leacture but found Sir Abul Bari awesome. In all his short lesson they made Algos easier for us to understand. Also the delivery of teaching methods are excellent. Jazak Allah

[xrlxdgi]

I am not a person with a Com S background but started to study algorithms from books ... I did not understand anything out of that ....But after I saw these videos...I throughly understood the concepts.. I believe rather than reading any books or any other resources one should watch these videos and you will have clear knowledge of algorithms. .. Thank you so much Sir.... I truly mean it ...

[dhzgdqd]

Great video. This is small adjustment, but I think a more exact answer for the average case of linear search will be Mu(n) = n/2 + n/(n+1). This is equal to n when n=1, and is just more than half otherwise. The reason for this adjustment is to count the probability of event(k not in array), when we also assume that each discrete event occurs with equal likelihood*.

(1) Let Mu(n) be the average time for problem size n
(2) The definition of mean is: Mu(x) = sum_over_x(x * p(x)), where x is the outcome and p(x) is the probability of that outcome

(3) In the case of sequential search, mu(n) = (1/(n+1))*sum_over_i( i ) + (1/(n+1))*n
NOTE: first term is outcomes where k is found in the array; second term considers the case where k is not found
(4) Substituting (1/2)*n*(n+1) for the summation, and simplifying, we get Mu(n) = n/2 + n/(n+1)

* This probably isn't a realistic assumption. P(k in array) = ? In reality we don't know and it depends on the instance of the problem. We would want to have some a priori estimate to feed into the calculations. Since k can take an infinite number of values, and i can take a finite number of values (1 <= i <= n), then a realistic average time is closer to the worst case time. How close to worst case? It will depend on the probability distribution of k. k is a random variable and should be modeled as such if we're doing probabilities. For algorithm design, using the worst case makes sense.

[madhulikamittal]

pls make videos according to net syllabus. ur way of explaining things are in a very natural way....u r too cool

[helperground]

set the speed to 1.25 and You will be able to learn faster. Thanks for this video.

[kritleenkaur]

U r too cool as a tr.should .I M preparing for net exams.in the age of 36..&wants to earn respect for me nd for my parents, as I am a mother of 2yrs old daughter....i can learn excellent if u can teach continuous with whole topics of c.s guide me to achieve success...

[snehasishsaha]

Sir Its too good explanation on the other hand where I opted for NPTEL course on Design & Analysis Algorithm, its confusing me makes it too difficult. thanks once again sir..

[adimadan]

Thanks Abdul Sir you explained it very well. Nowhere has this concept been explained all this well.

[pradipnitw]

interesting to know about min/max worst case.. never knew this fact..

[mirishfaqhussain]

wow i'm working as Backend developer and preparing for my interview, this series is just awesome