Why Comparison Based Sorting Algorithms Are Ω(n*lg(n))

[@BackToBackSWE]

Table of Contents: (and clarifications) Introducing Today's Topic 0:00 - 0:38 Ad 0:38 - 1:11 The Approach We Are Going To Take 1:11 - 2:12 Step #1: Crafting Our Decision Tree Example 2:12 - 7:20 Making Observations About Our Tree 7:20 - 8:58 Step #2: Drawing Our Generalizations 8:58 - 11:50 Step #3: Solving The Relationship 11:50 - 16:48 The Final Solution/Result We Can Bound 16:48 - 17:51 Closing Thoughts 17:51 - 18:36 Clarifications: 10:58 -> I wasn't clear about the n!. We will have n! leaves, at least, because there are n! permutations of the final array. We have to have at least that many terminal states in the decision tree since those are all the possible "final destinations" we can reach through our comparisons. 14:49 -> Correction to what I said: "And...if we add 0 that does nothing for us."

[@onurcanisler]

*You are awesome.*

[@shrshawn]

Hey ben, could you say what's the name of this music? As good as you teach, the music at the end touches the heart

[@larryd9577]

I've never thought that i would watch such videos for their entertainment value. But here I am, enjoying the neatly prepeared math.

[@BackToBackSWE]

nice

[@pathoslp]

Your attitude makes reviewing algorithms fun, thanks for the good vibes.

[@BackToBackSWE]

ye

[@scorpionesp6510]

bruh.. you just cleared up a semesters worth of confusion

[@sciphilo754]

Hey dude, I appreciate the tremendous work that must have gone to make this! You're too awesome man! Thanks a lot, never thought I'll be able to learn this concept as succinctly as you've done.

[@BackToBackSWE]

thanks

[@amalierovik9835]

Your videos are so good. I have studied algorithms for a while now, and I finally found your channel! I have used so much time on bad videos and explanations, but this is great. I think the reason for why I havent found any of your videos before is because of the titles. When Im looking for something I usually just type e.g. "Dijkstra", and yours are so long. Little tip maybe.

[@BackToBackSWE]

Thanks

[@KathrynSimone]

We learned this exact thing in class the other day... I was so confused and now I get it! Thanks so much! :) - UBC Comp Sci

[@BackToBackSWE]

nice

[@anoniem012]

Thank you, it is very good that you make checkpoints during the explanation, 'if you get this part you are good'. (Something like this you said if I recall correct).

[@BackToBackSWE]

ok

[@roadtoeternity7865]

@@BackToBackSWE "ok" , he literally doesn't care, LOOOOOOOOOOOL

[@NerdSnipingBatman]

Thank you so much for your videos ❤️ I got an offer from Amazon! 😀

[@BackToBackSWE]

Ay. Nice. Enjoy your time there, wish you a happy future.

[@adityakrishna11]

congrats man!

[@smilingowl4773]

Love the ending. Thanks for explaining, nowhere i looked explained it with enough detail and simplicity as you. Thanks!

[@rittyan]

Hey man, I really enjoyed the video and your energy. You kept the video so interesting and I really appreciate what you're doing. Subscribed!

[@amitbaijal421]

Simple Mathematical Explanation for a complex case

[@BusinessIdeas-]

think of the amount of effort and research he had done to put all this together ...... thanks a lot ,subscribed :)

[@BackToBackSWE]

yes

[@AkashRoy-do2dg]

this helped me out man. Thanks for the tremendous work you did there. each part was beautifully explained.

[@david31XD]

i just about to finish my first year at computer science thanks to you, your videos are the best

[@BackToBackSWE]

great! keep it up!!! a great field to be in

[@francescomanicardi8540]

Can you explain why it is valid to transform a summation of a function calculated with INTEGER indices into an integral (that takes the area under the curve, so it's not only the integer coordinates)?

[@BackToBackSWE]

I don't remember the math or the approach to be honest, I'd have to rewatch the video to remember

[@francescomanicardi8540]

@@BackToBackSWE Thank you very much for the honest answer!

[@Finn-jp6pn]

Hey! Videos like these help a LOT. Please make some videos on Masters theorem. I think I know the basic intuition behind it, but I'd love to know more. Thanks!

[@BackToBackSWE]

I'm making a website around this, it is pretty cool. You'll see it in 2-3 months.

[@Finn-jp6pn]

@@BackToBackSWEAwesome!

[@BackToBackSWE]

@@Finn-jp6pn Working on it rn. In the dark. :)

[@Finn-jp6pn]

@@BackToBackSWE haha...it's morning here, and I'm preparing for tomorrow's DSA exam. Your videos are a great help. Good luck with your website 👍

[@markgoldstein]

This was cool! I’d love to see more of these.

[@BackToBackSWE]

Eh, I think these are boring to be honest. I wanna start making more videos that are more..."me"....you'll see what I mean.

[@jahnavibodala2492]

The best way of teaching complexities.Thank you 😊😊

[@BackToBackSWE]

sure

[@tarsala1995]

I just decided to like every video you have :) Great content

[@BackToBackSWE]

nice

[@shanness237]

This is amazing, you are much better than our professer:) please keep doing it!

[@BackToBackSWE]

no, I'm a lot dumber

[@kinghassy334]

Thank you so much, I finally understand so many fuzzy concepts because of you

[@BackToBackSWE]

Happy Holidays! Really glad to help 🎉 Do you know about the 5 Day Free Mini Course? Check it out here - backtobackswe.com/

[@k.herzog2365]

"...for entertainment reasons" - me: laughing, then realizing that it is way past my study time and that i am actually watching this for entertainment. Great Videos!

[@BackToBackSWE]

nice lol

[@pshadoww]

14:48 I think you mean "if we add 0, that does nothing for us"?

[@BackToBackSWE]

yeah, I addressed that in the table of contents thingy

[@vestgaming7757]

Thanks a lot man. i was struggling a lot to understand it. its clear now

[@laharibasu9731]

Love the way you simplify things 💕

[@alitpani]

The best explanation ever heard... great job.

[@BackToBackSWE]

thanks

[@GameFlife]

teacher dif my teacher rambling while you make connections and connect the dot now my note they shine !!

[@miyamotomusashi4556]

Why can't my teachers show enthusiasm like this, I mean their lectures are fine and the explanations are OK, but they do it in a very mechanical way that I start day dreaming 5 minutes after the lecture starts. Anyways, great job brother.

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@shreyashi_music_art]

Thank you for the great video! But can you make a video on similar approach/proof for Comparison based searching using decision trees? I think that would be great to understand too!

[@sarfarazalam6077]

Thank you! Video was amazing and you explained the concept very well!

[@BackToBackSWE]

thanks

[@cocoarecords]

Hey i just stumbled upon your channel "really lucky" and i gotta say your style is very unique and clear any tips bro to learn data structures online too?

[@cocoarecords]

i was looking at this playlist but i am not sure if its enough? for example it doesn't cover nodes? excuse my ignorance kzbin.info/www/bejne/kJSYZZp8ncmjgqM

[@BackToBackSWE]

I have not many tips except practice a lot.

[@rafeekadrian]

Hey I really appreciate you efforts but what I know the maximum leaves would be the number of permutations of the array, which is 3! (3 factorial) for three elements. This is because there are six possible ways to arrange three unique elements on the other hand the minimum leaves will be 1 please correct me if I am wrong

[@soumyadeeproy6611]

always loved the way you teach !! Starting from beginning

[@BackToBackSWE]

ye

[@anktmshr]

I cant get the minimum no. of leaves. How is that n!

[@BackToBackSWE]

I remember no concrete information from this video.

[@gullraiznadeem2548]

I know this is from 2 weeks ago but i'll try anyway. First consider what the leaves actually are. Each leaf represents a sorted list. 1- There has to be at least one leaf that represents each possible list(There can be more than one). 2- Now considering we want to sort 'N' elements, you might know that a list of N elements can be ordered in N! ways or permutations(You can find videos on this if u dont understand how i got N!). So we will have at least N! leaves.

[@ahmed0thman]

finally a neat explanation for this point, thanks a lot 💕

[@epiclasersharks1866]

outro had me staring off into the night sky thinking about my place in the universe

[@chitrarajshekar3003]

Excellent explanation ! Thank you so much sir ....

[@BackToBackSWE]

sure.

[@BurhanKhan-m4h]

Sorry, but I am still getting confused as to why the maximum amount of leaves would be 8. Would it just be the individual elements that make up for the external leaves at the end of the last comparison? I might have just missed something, but other than that this video was very helpful!!

[@chaaaaaaaaaaan]

That was simple and understandable. Thank you!

[@theodoreajuyah4086]

Hey. I'm not a Comp Sci student; I've only looked up sorting algorithms on KZbin vids(especially MITOpenCourseware) so am not an expert but think I can weigh in here. Please correct me if I'm wrong. I thought the lower bound omega [Ω()] is the time it takes for the algo to finish sorting the best case input values i.e. the time to sort if you're really lucky with the array you're given. That would be the shortest possible depth of a leaf (e.g. on the leftmost branch of your diagram that compares A[1] to A[2], A[2] to A[3], A[3] to A[4], etc) which is n (in the best case of having an already sorted list) I say MINIMUM DEPTH of leaf/node as opposed to minimum number of leaves because only 'depth' number of comparisons are done one that branch. Some sources I checked were Wikipedia & GeeksforGeeks for best-case time where asymptotically sub-optimal algorithms like insertionsort & bubblesort actually have Ω(n) en.wikipedia.org/wiki/Sorting_algorithm www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/ Please let me know what you think, I'm doing some coursework on the subject and am preparing for interviews so look forward to seeing more of your videos. Thanks

[@BackToBackSWE]

Hey I don't remember much from this video to be honest - I knew this pretty well when I recorded this so recorded me should be trusted above current me

[@valkyriachronicles9717]

Heap Sort has O(n log(n)) complexity :) "I thought the lower bound omega [Ω()] is the time it takes for the algo to finish sorting the best case input values..." --> Be careful, complexity analysis is used to compute the runtime for different cases. (Best, Average, Worst) Normally people mean the Worst Case when they talk about runtime. Here that was the case. :D

[@Double_AV]

Your videos are awesome! Also did a recent video about a silicon Valley salary analysis get taken down or something? Or am I seeing things

[@BackToBackSWE]

Thanks, means a lot. Yeah, I fucked that video up. I have a new one I shot this morning that I'll post later today.

[@renyuanzhang9706]

I have two doubts: 1. # of comparisons is O(2^h) but you just showed h >= O(n log n), but h is not the final answer. 2. You change the discrete summation into an integral, that doesn't seem to make sense. Integral is the area under curve and it is the limit of sum when the step goes to 0, but there is no concept of limit whatsoever in your equation

[@BackToBackSWE]

I dont remember the math I'm sorry - rapid replying to comments

[@renyuanzhang9706]

@@BackToBackSWE How about the first question? Is the number of comparison 2^h or h?

[@valkyriachronicles9717]

@@renyuanzhang9706 I think you mean Ω, not O. :) 1. The number of comparisons is h. - You do not visit the whole tree to order your array. At each node it is either "". Both cases cannot appear for the same input. So the number of comparisons is the height of the tree. 2. He does not explain it. But if you compute runtime for Ω you actually use the limit. That is the known definition. Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } The inequation must hold for all n > n0. That is your limit.

[@nvaros3235]

g(n) = O(f(n)) if there is a constant c > 0 and a n0 such that c * f(n) > g(n) if n >= n0 So we have to show that c * n * log n > log n! for any n > n0 That is quite simple because n * log n = log (n^n) and n^n obviously is equal to or bigger than n! for any n above 0.

[@abdulmajeedmarek]

Superb, but i have a question why taking the integral from 2 to n gives us the minimum bound?

[@BackToBackSWE]

I wrote a long response then closed the comment response window....crap. Anyway, it is about the "window" we take the area of. If a function is going up (monotonically increasing) consistently, to get "less" to lower bound we can shift the window to the left. If it is going down (monotonically decreasing) consistently, to get "less" to lower bound we can shift the window to the right. Something along those lines.

[@footballCartoon91]

I am curious if we can create "quaternary search" that would be using the && operator or "or" operator..in terms of big O it is log base 4 to the power of n. And then "tertiary search",up until "10th search"

[@MiketheCoder]

Are you going to take Design and Analysis of Algorithms?

[@BackToBackSWE]

is that 451?

[@MiketheCoder]

Yup!

[@nataneeli8088]

the website is out now right ?

[@princejain8377]

would please cover segment tree algorithm implentation too??

[@BackToBackSWE]

sure

[@footballCartoon91]

This is what I am trying to do n also the log n of big O notation relationship

[@vishwaja1523]

this is so good. not good it's great. thank you for such amazing video

[@BackToBackSWE]

sure

[@tylersnard]

Excellent explanation, thank you

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@cord1778]

oh my god I love you! thank you very much. I just found a new internet tutor :)

[@BackToBackSWE]

ye

[@sagarchawla4892]

amazing explaination , love , love , love

[@swarpatel2927]

Perfect 👌🏽 explanation

[@BackToBackSWE]

ye

[@saraelgaily6308]

Perfect explanation

[@cocoarecords]

this channel doesnt have a potential but is a potential seriously quality content

[@BackToBackSWE]

what haha

[@dibyarupnath]

I am watching this video to better understand the logic behind omega(n log n), then he said "IT'S FOR ENTERTAINMENT PURPOSES", I have never felt any smarter in my life 😂😂😂

[@jwfu670]

thanks a lot，great lesson!😃

[@codewithbug]

just wow. thanks man

[@sharathkumark9692]

You are amazing man ❤‍🔥❤❤

[@ASHISHSINGH-nj6es]

Very Nice !!!!!!!!!!!!!!! Thanks

[@BackToBackSWE]

sure

[@becomeweasel]

Cool explanation

[@tsengyifan687]

Great job

[@BackToBackSWE]

thx

[@henokberhe6944]

Thanks so much!

[@rahil_rehan]

Dude, You are just awesome. I've been following you for a while now and I'm really motivated from you. One question though: how did you learn maths? And I would be really happy if you can make a video on your journey to becoming a pro at algos and programming.

[@BackToBackSWE]

Hahahaha, I'm not a "pro". I am a normal student. I'm going into my 3rd year at the University of Maryland College Park and this is just standard stuff you do in algorithms. None of it is me making novel discoveries. I just explain what I learn.

[@rahil_rehan]

@@BackToBackSWE (^_^), How do I start learning? Same here, I too am going to my 3rd year now. My university sucks! what would be your strategy to nail down big companies interviews in my next two years, I would really appreciate your suggestions, thank!

[@BackToBackSWE]

@@rahil_rehan Haha. Do a lot of Leetcode and deeply understand everything on this channel. That's basically what the interviews are about...algos and data structures. There is no "path". It depends on what you are good and bad at. That is for you to self-assess. But then just work on those things.

[@harshpatel105]

Thanks a lot for class bunkers like me! Anyways, university doesn't teach stuff! They want $$$. Thanks for providing good quality knowledgeable videos!

[@BackToBackSWE]

ye

[@rishabhpandey12aroll7.5]

thanks bro.

[@haojiaxiang4560]

thank you so much! just like a magic，i need to watch once again.

[@BackToBackSWE]

haha nice

[@notfound-bk5wn]

Thank u

[@BackToBackSWE]

sure

[@NinjasOfOrca]

It’s “number”, not “ amount”

[@BackToBackSWE]

ok

[@thomasjefferson6225]

Im kind of shocked that people consider this level of math complicated......

[@yhax909]

Thanks

[@ahmedboutaraa8771]

if interview > my_math_skill : return jokes

[@BackToBackSWE]

ok

[@usuuleymaabdallakadir8727]

A,B,C,D,doit

[@arctan-k]

Well, as a mathematician I cannot ignore a few mistakes that you made. Firstly, you cannot just say that integral is equal to the sum. In this case, it is true, but in general, it is false. I remember watched interesting proof for this integral. If I will find it, I will attach it in the comment. Secondly, distribution on the 15th minute is incorrect. The base of the log should be 2, not e. In general, it was an interesting video, but you should not break your explanation, because it breaks the focus.

[@surjayanghosh5872]

Why are you so afraid of showing the Math ! You don't need to tell "dont worry about the math" Everytime you do some Math!

[@BackToBackSWE]

Hahahaha, because: 1.) Most of the time it is me half lying because I haven't done it myself or I don't understand it. 2.) It would alienate half the audience who as soon as they see a summation or constructive induction will tune out 3.) It would increase prep and production time since once you make a video, it is permanent. A math mistake can't be "erased over" in video format so great care must be taken to make sure everything is right. In this video's case (and I remember doing it) I had all of the equations. I probably said this due to #2.

[@surjayanghosh5872]

@@BackToBackSWE Haha. Fair Enough. Good video. keep up the good work! :)

[@eshandhok2591]

Gold

[@kylea8968]

支持一下

[@BackToBackSWE]

谢谢！

[@Raj_Patel21]

Cool

[@BackToBackSWE]

hey

[@xiuwenzhong7375]

finally, updated again. ha

[@BackToBackSWE]

hey