A Detailed Algorithmic Analysis of Insertion Sort. Best Case & Worst Case.

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Give exact comparisons and moves that happen in the best, average, and worst case of insertion sort.
Gauss' Trick: mathcentral.uregina.ca/qq/data...
Bubble Sort Analysis: • An In-Depth Algorithmi...
I'm so sorry that my camera was about to die. I had to cut the video short. The average case is the hardest part to understand so this video also would have been much longer.
I'm not sure if I will ever cover it in a video...so there's a really hard challenge. What's the amount of comparisons and moves for the average case? (the hard part is calculating the expected value for the total while loop comparisons)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech

[@BackToBackSWE]

Table of Contents: We Have Come A Long Way pt. 1 0:00 - 0:37 Behind The Scenes 0:37 - 1:00 We Have Come A Long Way pt. 2 1:00 - 1:23 What We Are Going To Cover In This Video 1:23 - 2:02 Walking Through The Pseudocode 2:02 - 3:08 What Is A Sentinel? 3:08 - 3:37 The 2 Fundamental Operations: Moves & Comparisons 3:37 - 4:59 Starting The Actual Insertion Sort Walkthrough 4:59 - 14:25 Best Case: Exact Amount of Comparisons 14:25 - 17:28 Best Case: Exact Amount of Moves 17:28 - 21:08 Worst Case: Exact Amount of Comparisons 21:08 - 28:55 Worst Case: Exact Amount of Moves 28:55 - 34:45 Sorry...The Camera Was About To Die 34:45 - 35:06 Wrap Up 35:06 - 36:19 The code for this problem is in the description. Fully commented for teaching purposes.

[@rishabhjha447]

Watch Ravindra Babu Ravula's Video on KZbin.

[@rishabhjha447]

kzbin.info/www/bejne/eICUZWh-frp7iMk

[@dreamzsiva]

I love how this young guy who is still pursuing his degree is so well articulated in his thoughts as a teacher and proficient as a coder. You will go a long way buddy! I am buying your interview class.

[@BackToBackSWE]

hahahahaha, ok, I'm just a dude...and I'm wrong a lot

[@sushruttabakade6088]

I'm crying here, for the past one hour I was struggling with all of these complex concepts and how wonderfully you in just half an hour taught me everything. Thank you man, excellent video!

[@BackToBackSWE]

hahahahaha nice.

[@mariasandru5566]

These videos are so underappreciated. I can t believe it.

[@BackToBackSWE]

yo

[@fortresssanitarium2205]

This is what I'm talking about when I tell my parents what a teacher should be like. The passion that u display is alluring. Thanks for doin this buddy

[@superchillh3o]

I love the way you explain things, the clarity is unmatched, thanks so much.

[@BackToBackSWE]

sure

[@GamerGabbar]

THANK YOU SO MUCH FOR MAKING VIDEOS LIKE THIS! I'm an Indian but I don't live in India and most videos like these are made by people from india, They're excellent videos but hard to understand. This is super nice! Again, Mad Thanks! 🙏

[@BackToBackSWE]

Nice sure

[@bronzebond4869]

Bro you are doing a great job explaining all this. We appreciate the work you put in. Thanks again.

[@zainabsherani8950]

You're in my Algorithms class!!! WOW! Keep up the good work! The analysis portion helped me out!

[@BackToBackSWE]

Hey, good. Sometimes I wish I could go up there and hammer out tiny things I KNOW are confusing students. Everything should be taught the way a student can pick it up quickly. I wish I could post in Piazza, but I don't wanna spam people. But I really think these videos would help people. I want to do a video for every lecture topic we do.

[@fredericoamigo]

Thank you so much for this! Brilliant vid! Keep up the good work!

[@maike3530]

I can't even express how thankful I am for your videos! They help me a lot in my studies! Your videos are amazing :)

[@margaritasmoliakova7084]

you are so good in explaining things!!! THANK YOU so much for the videos!!!

[@vineetsharma4121]

Superb analysis!!! I had been searching for such complete analysis for so long; finally got it here.

[@BackToBackSWE]

great

[@techservices7028]

most videos and books did not indicate that A[0]=-infinity. This video really helps to understand. Thanks!

[@warrenbinder3612]

This is one of the best and most detailed videos about the best and worst cases of Insertion Sort. You explained the topics really well, they were easy to understand. F in the chat for your camera battery, the average case sounds interesting!

[@BackToBackSWE]

Glad it was helpful!

[@nadasa208]

Thank you for this really perfect explanation !!

[@js4466]

Your attitude and presentation makes learning fun and clear. I wish you the best in your future endeavours. Liked and subscribed.

[@anrihek5701]

351 has just been such a confusing thing for me, even though I take a lot of notes and read through them I just don't get it. The analysis videos have been really helpful and they are much easier to understand than lectures. I know making these videos must be really time consuming and youtube channels seem to grow really slow sometimes, so I just want to say again how much I appreciate this and your work has been so meaningful.

[@BackToBackSWE]

sure. Yeah, I assume you have Teli...I personally like Teli as a fundamental human being but his speed sometimes loses people. The problem is conceptual examples. If you speak what you see in your head...you have very few sentences before you begin to lose half the audience who weren't paying attention to your entry into a conceptual explanation...if that makes sense. This is why, when teaching it is critical to use visuals, be slow, and make sure that what is in your head...is on the board...not in words. Words lose people.

[@NasK330]

Oh man! You can't tell how thankful I am for this video!

[@BackToBackSWE]

Happy Holidays 🎉 And we are thankful for your comment, NasK! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

[@khadijaanam62]

You are doing great! You are awesome at what you do!!! YOUR VIDEOS ARE SO DAMN HELPFUL! Keep up!

[@BackToBackSWE]

thanks

[@sohanaggarwal8770]

Enjoyed the presentation. Explained clearly.

[@leahkelley8452]

I am a CS major and your videos have honestly clarified the majority of the concepts that my professors failed to teach. Thank you for doing this. It is extremely helpful. :)

[@BackToBackSWE]

I think we are in the same class probably. I go to UMD. In algos rn.

[@leahkelley8452]

Why are you in algorithms? I thought you were a grad student?

[@BackToBackSWE]

I'm a 2nd year.

[@leahkelley8452]

Are you in Teli’s class? Did you transfer from a different school? ... what is your name?

[@BackToBackSWE]

Yes. I'm in your class probably haha. Section #0201. My name is Ben.

[@user-yb6oc4tj2w]

Man!!!! Best videos on algorithm ❤️

[@BackToBackSWE]

thx

[@procode6881]

Hats off to the best explaination on insertion sort

[@lorenzozuluaga4309]

wow lend me tell you you got a new subscriber, really apprecciate that you give to us all this knowledge, bless from colombia!!

[@BackToBackSWE]

hahaha wassup from america 🌽🌽

[@zeffanayahyisrael8428]

Yes this is EXCELLENT Work. Please continue. Thank you very much for your knowledge

[@BackToBackSWE]

thanks

[@cameronsantiago3155]

The Grind! The hussle!

[@thanhtungtran8249]

Thank you for super great videos

[@supamdeepbains5172]

You’re videos are really helpful ive got exam tomorrow and they’re helping

[@BackToBackSWE]

nice, umd?

[@osandarathnayaka9002]

cool explanation thanks.

[@joel_b9216]

broooooo.... duuuude!!!!! You're AMAZING. way better than my 50mins lecture

[@BackToBackSWE]

no u

[@KixMayne91]

OMG I EFFING GET IT!!!!!!! Thank you so much, it was throwing me off thinking that the while loop was always supposed to execute n-1 time since its still a linear process. But now that you clarified it, will ONLY execute n-1 times if it never performs the swap operations. Other wise its performing n(n-1)/2 when it compares and swaps and compares again, etc... Thus making N^2 the average case since there will be moments where the comparison and swap occurs in an unsorted array.

[@BackToBackSWE]

great lol and tldr tbh im fast replying to comments I luv u tho but I dont remember any specific math it is very much on the spot

[@cerenarkac3484]

Thank you very much for this useful video

[@BackToBackSWE]

Glad it was helpful!

[@dead_gawk]

The thought of putting in 6 hours of work everyday, just so that some random person on the internet would get free education is amazing. Respect to you, Champ.

[@fabriciopolicarpo3725]

You gave me keys bro. up to now I understood everything but that forsaken arr[j + 1] = current. Now I understand the entire algorithm mechanics.

[@zaintahir3348]

THANK YOU!!!

[@ashishm8850]

Kudos to you! Thanks!

[@BackToBackSWE]

ya

[@hakancemgercek]

14:10 I'm brave enough to stay with this video because I'm trained to stay in the class while the tutor told everything which I didn't understand about this course XD. But thanks to you now everything "finds a home" in my brain. THX

[@BackToBackSWE]

thanks

[@andrewnguyen6396]

thank you so much :)

[@iambongani]

The only way to appreciate these videos for everyone is to share them. Come on guys lets show some appreciation

[@BackToBackSWE]

lol

[@laggynacho]

Great Video!

[@BackToBackSWE]

Happy Holidays 🎉 Thank you for your kind words! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

[@aaishikighosh6154]

Tysm for this.... I am 18 and I am starting out on these subjects... Nd you really make these easier to understand...

[@BackToBackSWE]

great - you can go so far in this space, get good young

[@Rahul-yg5kp]

Wow man great video.

[@BackToBackSWE]

thanks

[@vishwassrinivas474]

Awesome,please do a video for finding the longest palindromic subsequence.

[@BackToBackSWE]

Yes, it's on the list, it'll come one day

[@paulpassiglia9997]

Thank you so much

[@BackToBackSWE]

sure

[@esraataher36]

a very useful one

[@booboo-oh1vd]

OMG... THANK YOU

[@JustJoelTV]

Your clarity is next level. Thank you. Great video, thumbs up and sub from me

[@BackToBackSWE]

Thanks for the sub!

[@guowanqi9004]

6:09 29 will trample over 10's value. 6:24 10 is still looking for a home. Dang that seems so sad

[@BackToBackSWE]

indeed

[@alirezaRahmanikhalili]

it is most useful video ever.

[@BackToBackSWE]

haha bold statement

[@sajidsarkar9574]

Can you cover algorithm strategies: Brute Force, Greedy, Dynamic Programming, and Divide and Conquer?

[@BackToBackSWE]

maybe

[@user-ti2kd2yo1w]

thaaaank you

[@sujithkrishnan6429]

Wonderful videos, it would be great if we have sequence number for Videos, to follow easily,Thanks

[@BackToBackSWE]

thx

[@alannah000]

You are awesome

[@lernordmac2711]

0:01 Rock on dude

[@BackToBackSWE]

what did I do

[@saadmahmood5396]

is there a video where you explain the average case for insertion sort?

[@fr.ae_]

If only Nigeria lecturers teaches this way... The problem now is I understand yours but it's totally different from what I was taught in class and the lecturer expect me to write the exact thing he taught in class 😢 if not I'm not getting my full mark... Anyways thanks this your video was very helpful 🎉

[@BackToBackSWE]

Happy Holidays 🎉 What's important is getting your concepts clear! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

[@noursafa22]

do the average case pls

[@Happy-on2is]

Hii Mr I got a doubt 🤔🤔 actually in worst case moves it is 1 + (summation of i = 2 to n) 2 + (summation of j = 1 to i - 1) i right ??? but you have mentioned 1 + (summation of i = 2 to n) 2 + (summation of j = 1 to i - 1) 1 difference is the last 1 and i in the above expression

[@BackToBackSWE]

im not sure - I don't remember the math

[@Happy-on2is]

@@BackToBackSWE 🙄😕

[@uzboxing5238]

Listening to this at 1.75 speed and enjoying it!

[@BackToBackSWE]

hahaha, I recommend everyone do that for learning vids. I do podcasts 1.5x and videos 1.5x-2x

[@uzboxing5238]

@@BackToBackSWE actually, after my comment I tried 2x too, very effective. Thank you for the videos. They are helping a lot!

[@BackToBackSWE]

@@uzboxing5238 nice

[@faysalahmedakash7703]

why the number of comparisons for worst case is not "n(n-1)/2" ? Won't the ith element do (i-1) comparisons to get into the 1st position?

[@AK-cl8iv]

reference: when i = 2, j = 1,0 ; i = 3, j = 2,1,0.... i = n, j = i-1, i-2,...,0 hence total number of comparisons for worst case is 2 + 3 + ... + n = n(n+1)/2 -1

[@viktorvostrikov9625]

Thanks! Amazing series.., I watched bubble sort, but I still can't understand why you do you get (n-1) from the while loop set? How can you calculate bounds and say that it answer is n-1? Why when you can't use same approach if outer loop would not be 1?

[@BackToBackSWE]

can you timestamp it?

[@viktorvostrikov9625]

@@BackToBackSWE 16:30

[@BackToBackSWE]

@@viktorvostrikov9625 Ok so best case comparisons. We get n - 1 since that purple section will get hit n - 1 times and NEVER get entered in the best case (the array is already sorted...nothing needs to go backwards for insertion).

[@viktorvostrikov9625]

@@BackToBackSWE yes I get that, you will do only one comparison in for loop. and after all comparisons the purple area will be hit n-1. I just don't get the math of it and how you managed to convert Set from j=2 to n, to be equal to n-1. I thought that set supposed to mean 2,3,4,5,6...n. So you should sum all that and then you will get complexity, which is different than n-1.

[@BackToBackSWE]

@@viktorvostrikov9625 If j goes from 2 to n, how many iterations happen? Imagine n is 3: j = 2 j = 3 2 iterations. n was 3. So n - 1 iterations that the if statement is hit.

[@loganynguyen]

What uni are you at?

[@BackToBackSWE]

This one umd.edu/

[@JustSoji]

How different are comparisons and moves if we don’t use a sentinel

[@BackToBackSWE]

what do you mean "how different"

[@JustSoji]

Back To Back SWE will the number of moves/comparisons change if we don’t use a sentinel

[@JonnieZuramski]

Do you think you'll eventually do average case?

[@BackToBackSWE]

no, I should've but it sucks and would've added 30+ minutes to recording time, are you in 351?

[@laxmipoojaanegundi7757]

Can I be part of Back To Back SWE? I can assist in any work. Its so exciting to be part of Back To Back SWE

[@BackToBackSWE]

Yeah, I'm looking for writers that are good

[@yoshi4980]

u didnt do average case :( but otherwise great video.

[@BackToBackSWE]

I know :(

[@abemelekdaniel8913]

fine

[@CarolinaRutiliLima]

I wanted the average case aaaa

[@bhargavsai2449]

System.out.println("Superb");

[@BackToBackSWE]

thx

[@volkanulker6432]

Can you add subtitle to these contents ?

[@renjieyu8700]

Ben, love u 🤣 我想当你的小迷弟啊啊啊，Now, Let's deal with the sort problems

[@BackToBackSWE]

I want to be your brother too

[@zkfdsldfjsdjfl1]

I used to take Fawzi’s 250 in that classroom 😂

[@lernordmac2711]

You could see Stamp from the windows if it was daytime I miss it lol

[@zkfdsldfjsdjfl1]

@@lernordmac2711 YO the good times

[@BackToBackSWE]

yeah it is in ESJ, top floor, all the way to the left.

[@BackToBackSWE]

@@lernordmac2711 could u? I don't think u can but u can see Hornbake.

[@BackToBackSWE]

@@zkfdsldfjsdjfl1 yes

[@JustSoji]

But what about average case

[@BackToBackSWE]

uh

[@bhargavsai2449]

plz attach java code

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@supamdeepbains5172]

did you listen to eminem new album? music to be murdered by?

[@BackToBackSWE]

yeah

[@ahmadbodayr7203]

Read About Islam bro and thank you for your great explaination❤❤

[@muhammadrezaulislam9999]

there was no average case. -.- i watched the whole video for average case but nope. -.-