I like your lectures but it could be greatly enhanced if its more slower. Sometimes, I have to run the CC to cope with your speed and this makes me lose focus. However, up till this lecture, things seem great. I will update in later lectures though
we are programmers! if you are using Chrome, just type the following code into your js console in developer mode for a x0.9 playback rate or any other number your ears prefer: $('video').playbackRate = 0.9;
I cannot understand 6n*(logn + 1). I think it should be 6n*logn. It is true that the number of levels is logn+1. However, the work is done when moving from one level to the level above it. (From 1:00AM to 5:00AM, there are 4 hours, not 5 hours; from 5th floor to 8th floor, we need to take stairs 3 times, not 4 times). Both reaches O(nlogn) time complexity. But I just don't understand 6n*(logn +1). I have checked the prestigious book "Introduction to Algorithms" by Cormen, Lerserson etc. It also states it is cn*(logn+1) and finally it is O(nlogn) time complexity. On the other hand, several you-tube merge sort videos agree with my thinking. Nevertheless, merge sort time complexity is O(nlogn).
This initially confused me as well, but it made sense once I plugged some numbers in. Log(1) == 0 so if the runtime was 6n*logn like you propose, then an input array of length 1 would take 0 time to sort. This would be incorrect, because the algorithm still needs to "sort" the array (even though it is length 1) by running the merge operation on it and this merge operation takes 6n steps.
amazing explanation. thanks:).. Looking forward to all other videos
Awesome Explanation !!!
amazing!
amazing
This lecture is interesting! :)
Wonderful!! It is just so beautiful!
Could you please provide a like to the slides ? thank you in advance.
But recursion trees are not proofs, they are just used for visualizing and give us some idea about what the time complexity might look like.
I like your lectures but it could be greatly enhanced if its more slower. Sometimes, I have to run the CC to cope with your speed and this makes me lose focus. However, up till this lecture, things seem great. I will update in later lectures though
You just need some practice.
Gear | Playback Speed | 0.75
we are programmers!
if you are using Chrome, just type the following code into your js console in developer mode for a x0.9 playback rate or any other number your ears prefer:
$('video').playbackRate = 0.9;
0:00
0:40
If n = 4 the number of levels j = 0, 1, 2. The maximum level is 2.
But log n base 2 + 1 ≠ 2.
You need to count the root level too
I cannot understand 6n*(logn + 1). I think it should be 6n*logn. It is true that the number of levels is logn+1. However, the work is done when moving from one level to the level above it. (From 1:00AM to 5:00AM, there are 4 hours, not 5 hours; from 5th floor to 8th floor, we need to take stairs 3 times, not 4 times). Both reaches O(nlogn) time complexity. But I just don't understand 6n*(logn +1). I have checked the prestigious book "Introduction to Algorithms" by Cormen, Lerserson etc. It also states it is cn*(logn+1) and finally it is O(nlogn) time complexity. On the other hand, several you-tube merge sort videos agree with my thinking. Nevertheless, merge sort time complexity is O(nlogn).
This initially confused me as well, but it made sense once I plugged some numbers in. Log(1) == 0 so if the runtime was 6n*logn like you propose, then an input array of length 1 would take 0 time to sort. This would be incorrect, because the algorithm still needs to "sort" the array (even though it is length 1) by running the merge operation on it and this merge operation takes 6n steps.