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

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

I found this proof in my algorithms class notes. I think I explained this decently.

++++++++++++++++++++++++++++++++++++++++++++++++++

[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."

[larryd]

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

[pathoslp]

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

[NerdSnipingBatman]

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

[scorpionesp]

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

[sciphilo]

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.

[anoniem]

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).

[amalierovik]

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.

[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

[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!

[smilingowl]

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

[miyamotomusashi]

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.

[epiclasersharks]

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

[francescomanicardi]

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)?

[k.herzog]

"...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!

[markgoldstein]

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

[Finn-jppn]

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!

[AkashRoy-dodg]

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

[BusinessIdeas-]

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

[vestgaming]

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