Somebody took their clever pills when they came up with that argument. But part of its ingeniousness is that it is easy to understand for the rest of us. This one is simple enough that, if you show students what a decision tree is, you an guide them to discover the rest of the argument on their own.
It seems like the channel has been around long enough, but it hasn't happened yet, so I don't expect it to happen. But perhaps someday Alan Turing will look down from above and deem it worthy of a larger audience...
It seems reasonable to not have that analysis be part of this video, but maybe I should link to an explanation. But, because log (product) = sum (log), taking the top half of the factorial terms (each at least n/2), we can see lg n! Is at least (n/2) (lg (n/2)) = (n/2) ((lg n) - 1), where the lower bound is easier to see.
@@AlgorithmswithAttitude I see :) In my opinion, if the explanation fits into 1-2 lines, why not include it in the slideshow, since the result may not be clear to everyone? On the other hand, one could also argue that since the proof isn't that hard, it could be left as an exercise.
I always thought this proof was some crazy-math-heavy thing, but you explained this so well that it now seems too simple!
Somebody took their clever pills when they came up with that argument. But part of its ingeniousness is that it is easy to understand for the rest of us. This one is simple enough that, if you show students what a decision tree is, you an guide them to discover the rest of the argument on their own.
I want this channel to blow up. This is the best algorithm channel on youtube
It seems like the channel has been around long enough, but it hasn't happened yet, so I don't expect it to happen. But perhaps someday Alan Turing will look down from above and deem it worthy of a larger audience...
Thank you, the explanation is great! The only thing I had to find more details on was why lg(n!) = Ω(n lg(n)).
It seems reasonable to not have that analysis be part of this video, but maybe I should link to an explanation. But, because log (product) = sum (log), taking the top half of the factorial terms (each at least n/2), we can see lg n! Is at least (n/2) (lg (n/2)) = (n/2) ((lg n) - 1), where the lower bound is easier to see.
@@AlgorithmswithAttitude I see :) In my opinion, if the explanation fits into 1-2 lines, why not include it in the slideshow, since the result may not be clear to everyone? On the other hand, one could also argue that since the proof isn't that hard, it could be left as an exercise.
Thanks!
Couldn’t get where 2^h was coming from and why n! ≤ 2^h in my other source of learning algorithms, this video helped 👍
Mind blown!!! Love it
Why does the insertion sort for loop start from 1? Because elements in arrays start from index 0..?
Yes. The first thing we do is insert the item at index 1 into the (trivially already sorted) list of one item ending (and starting) at index 0.
@@AlgorithmswithAttitude Got it, thanks!
keep up good work!
That was perfect
Thanks man