Analysis of Merge sort algorithm
Vložit
- čas přidán 5. 07. 2013
- See complete series on sorting algorithms here:
• Sorting Algorithms
This is part 2 of our lesson on Merge sort. Merge sort is a divide and conquer algorithm that has worst case time complexity of O(nlogn). In this lesson, we have analyzed the time and space complexity of merge sort algorithm.
See first part of this lesson here:
• Merge sort algorithm
Series on time complexity analysis:
• Time Complexity Analysis
For more such videos and updates, subscribe to our channel.
You may also like us on facebook:
/ mycodeschool
I just noticed that when analysing time complexity, he color codes each operation by type:
Teal = Simple actions
Red = Loops
Purple = Recursive calls
That makes it so much easier to follow!
instablaster...
WAYWAYWAYWAY better than my prof's lecture
Best part, the videos are in the cinematic aspect ratio, so they look awesome on ultra wide monitors!
The quality of these videos is amazing. The aspect ratio is perfect, the voice is clear, and I love how they use different colors for functions, recursion, and loops. It's crazy to think that this quality is from almost 10 years ago
this is the best that I have seen on Merge sort complexity
absolutely amazing channel ! you are a GREAT teacher thank's alot keep up the hardwork
Thank you so much! I needed to understand mergesort for a college activity, and this was the clearer and best explained method i've found :D
Wow, his is 2013 video. I'm watching it in 2020 to sit for my campus placements. Great explanation👏💕
The simple thing is : There will be logn levels to divide the array up to 1. and then for each level merge function is applied which itself takes 0(n) time. Therefore multiply n with the total step taken which is logn. The overall time complexity therefore boils down to 0(nlogn).
Array of size 8, how many levels up to 1 ? 4>2>1 which is 3; log 8 base 2 is 3
Best computer science videos on CZcams. Kudos to you sir
Presented really well visually & orally. Great Work...!!!
Thanks a lot for being my Base Case of searching a Merge Sort Tutorial which will provide me details explanation. And of course, better than my Prof's lecture. :)
brilliant teaching!! I wish my Professors could teach like this!
thanks for the awesome lectures ....please upload the rest of the lectures like heap sorting ,etc
Translations: "into" = "times" or "multiplied by"; "by" = "divided by"; "upon" = "over" or "divided by"
Thank you for the cultural translation. :)
haha. Cool !
One of the best video explaination of time as well as space complexity !!
Such a wonderful explanation! Thank you so much.
this guy is actually a god. perfect way of explaining hard concepts
Yes, We are reducing the expression at each step,, So, K is starting from 1 and increasing till we reach T(1) .. You can either reach me here or write to mycodeschool [AT] gmail [DOT] com
Why the memory consumed in stack not taken into account like in the space complexity analysis of fibonacci, exponential modulation etc
Hey Man do you know how great work you are doing for others ? people like you makes the world beautiful :)
Unfortunately he is dead.
Incredible explanation, thank you so much!
Your videos are so interesting, always forget to like. Thank you Sir for such clear explanation and hope for more videos
Hi Shanmuk,
What is it that you do not understand? I can try explaining. Well, maths and programming go together. But, you don't always do such complex calculations to figure out time complexity. Recursion is tricky. I am sure you know enough maths to be able to program, that's why you are here. If you are not getting anything in this tutorial, ask specific questions.
I am having a hard time to follow the time complexity calculation. Maybe I don't know logarithmic and could be the reason. how come T(n/2) would become 2T(n/4)+c'(n/2). where does the c' come from? and i do not understand how 2^log2n T(1) will become nc. maybe it's just me but I could not follow. But thanks for doing this work. Appreciate it. If possible please try to do another video.Thanks
Best explanation I found on youtube till date :)
A fascinating explanation as expected, just as a remark, we could use master theorem and get the complexity easily
This is better explenation about it than I never said, thanks a lot :)
hey.. thanks for the great work. Will be good to have videos for Bucket Sort, Radix Sort and Searching Problems (Sequential Search, Binary Search etc)
Great video, thank you for your clear explanation.
Awesome explaination..i was just looking for an easy explaination..and you ended my search..;-)
thank you for your help! I really enjoy watching your videos :)
I guess the Big-O notation is more famous !
Big O gives the worst case scenario that is the tightest upper bound.
While Theta notation is for function bounded between two curves from down and above.
Thank you! I needed a video to explain the formulas
thanks for giving us this. super helpful and clear. gj
bro you are an great mathematician
Could you tell me the time complexity bcoz i am getting 0(n2) because comparing and moving is present
liked the space complexity explanation :)
My respects for #HumbleFool
He is not humblefool . He is animesh nayan
@@AyushGupta-mm4jg he is Harsha Suryanarayana from IIIT Allahabad
#humblefool
@@RAHUL-gf3ft he is Animesh Nayan , if you want to hear to audio of Harsha Suryanarayana , then access the Euclid's GCD Algorithm on mycodeschool.
@@RAHUL-gf3ft this iiitA people just💥🦸♀
@@navyasri5077 Proud to be an IIITian
Can you give a link to logarithmic laws required to solve recursions ?
Great way of explanation...loved it❤❤❤
SIR PLEASE UPLOAD VIDEOS ON HASHTABLES
Wow!!!! Awesome explanation. Didn't knew about theta complexity. Everywhere I saw it was big Oh only. And many do not bother about space complexity. Thanks a lot. Please upload videos on heap sort also. Also sir if you could do some difficult time complexity questions on sorting algorithms, it will be very helpful for entrance exams (GATE etc.) Thank you sir!
This great programmer is not between us.
fossiiita.github.io/humblefoolcup/humblefool/humblefool.html
far more better than my teacher's lecture!
excellent explanation, thanks for the video
Thanks for g8 explanation sir i got clear picture today on sorting .But i am confused when u said to clear extra memory but as these array is store in the static section it is deleted itself .sir Are u taking in case if it is store in heap section?
Thanks a lot :) It is really helpful
mycodeschool at 9:13 are you using plug & chug method?
At 16:38, I think at level 1 it is n/2 (not n) because we are using only n/2 space, we didn't even entered the right recursion tree. Same goes for the next level, n/4, then n/8 and so on. So, the total space would be n/2+n/4+n/8+.....+1 (or may use infinity for simplification), and not n+n/2+n/4+....+1. But, anyway, it would be in O(n).
Correct me if I'm wrong.
I would have porbably joined for a course if you had provided..... No body can ever get these basics in such an interactive way you're providing us with...
Still You are the best Bro....Just watch your videos to revise topics :)
what to return on the base case of mergesort function?
Here for space complexity and absolutely worth it alhamdulilah
At 6:56 why is the complexity of Merge() C3.n + C4? Why is it not C3.n?
how to calculate the time complexity of creating left array and right-array
TH BEST EXPLANATION ONE COULD EVER GET.. :) HaTS oFf
PEOPLE WHO SO EVER HAVE DISLIKED YOUR VIDEO MUST BE UNIVERSITY PROFESSORS BCZ THEY MUST BE JEALOUS WITH YOUR TEACHING EFFICIENCY.
Great videos, thank you so much
Why is n/2^k = 1 at 9:29?
And also, why at 10:06, 2^log2n = n?
We can't determine T(n/2^k). But we need to get rid of T(n/2^k), and we know the T(1) = 1. Hence, we replaced with T(1). How T(1) is 1? Think up of a merge sort having 1 element will sorted in 1 unit of time. And, answering to your second question, log of n base 2 returns "x the POWER of 2 which equals to n". We are powering with the same number i.e. x (the POWER of 2) again, we'll get n. Try with some examples, you'll get it. ex: Base is 2. n = 8. Evaluation: 2 ^ log 8 = 2 ^ 3 = 8.
Thanks! this is perfect
You are the best, man
Thanks a lot man!
nice video thanks very much.. its really helpfull
5:47 I don't understand. It should be n/2 right?
wat is the need to again calculate the time complexity ?
just had a small doubt if someone can explain (may be a dumb one..:/ ) When calculating T(n) array is divided into 2 parts so the k is incremented in every step. But I am confused with the calculation. How 2T becomes 4T and cn becomes 2cn.
It's done recursively, basically just keep plugging in T(n/2) -> T(n).
Hi, should not the space complexity be O(nlogn) ? When the left half is completely decomposed, it occupies "(n/2)*logn" space (logn steps) and the right half takes n/2 space. So total space is n/2*logn + n/2 which is equal to nlogn space.
How ? Extra space required is just n; left subarray plus right subarray
thank you thank you thank you so much you are a life saver !
Sorry, I don't understand when calculating T(n) in 08:52 why T(n) = 2*T(n/2)+c'*n = 2{ 2*T(n/4)+c'*n/2 } + c'*n. Why we need to add c'*n in the end? and it also add c'*n in the following steps afterwards.
+apo tessar Because it is recursive function. So for example on 8:52, on the second black stroke he has 4*T(n/4) from this he looked what was exactly T(n/4) equal to, so by the same formula he gets 2T(n/2/2) + cn, when plugs in n/2 to general formula. It is same as 2T(n/4) + cn. than he multiplyed by outer 2 which was there before and got 4T(n/4) + cn. The second cn comes from the same function for n/4 written recursively and other cn stays there as before so at last he added them and got 2cn. this get done K times so recursivley he gets kn. Maybe its bad explanation but its hard to explain by words ))
I still cannot understand it... like, if we expand 2{ 2*T(n/4)+c'*n/2 } + c'*n, it would be
2{T(n/2) + c'*n/2 } + c'*n =
2*T(n/2) + c'*n + c'*n =
2*T(n/2) + 2c'*n
compared to original
2*T(n/2)+c'*n
There seems to be an extra c'*n...
Why...?
+Hang Chen what are you talking about? When you expand expression of course it wont be the same as original..because you are using T(n/4) to evalute instad of T(n/2)
He is expanding the whole recursive formula to show you how to get idea of time complexity. Its easier to understand what is going on when u follow original formula..
czcams.com/video/g1AwUYauqgg/video.html
please can anyone explain to me what is n and from where we get it in O(nlogn) -space complexity "in case we do not clear extra memory" ?
Hi, what is n0 in your video?
Good explanation.
+mycodeschool hi, for the second step, I don't understand how'd you managed to get from c'n to 2c'n. Isn't it supposed to be c'n(1+1/2)?
we have to figure out the running time of two recursive calls on n/2 elements. Each of these two recursive calls takes twice of the running time of mergeSort on an (n/4) element subarray (because we have to halve n/2) plus cn/2 to merge, that's where you get the extra factor.
very nice explanation!!!
what a nice way for teaching.. great man!!
please upload count and radix sort algo
thanks
This great programmer is not between us.fossiiita.github.io/humblefoolcup/humblefool/humblefool.html
@@shashanksahu1971 the narrator "Animesh Nayan" is alive and working at Google. His friend and co-founder Harsha died in car accident. Most of the videos are done by Animesh.
hank for play lists
Thank you so much for this video. I have a question. I usually get confused when calculating the complexity of recursive functions. In this case why is it log n (I know that's the correct answer but why so)?. We have two for loops with complexity of O(n) which is greater than log n. Why don't we derive that the complexity of merge sort is simply O(n). Also since we are going to visit all the nodes in the tree, the complexity should be O(n) right? It'd be very helpful if you can explain this to me.
It will be binary tree with two nodes always and height of binary tree is logn
You are really awesome sir
thank you thank you thank you!
Very helpful!
can u plz make a video for greedy algorithms nd dynamic programming
this guy is dead
what the fuck?
Yes that's true
fossiiita.github.io/humblefoolcup/humblefool/humblefool.html
It's sad as fuck ....
Manas Chakrabarti wow smh
awesome explanation.........!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
thanks for the video.
is this information really necessary outside of college?
Yes! it is. If you're targeting to work at top organizations. you are expected to know how to analyze your code complexities and optimize if possible.
Your videos are so good. Thanks a lot !!
Gülsüm hanım nasılsınız? Yedi yıl geçmiş aradan şuan ne iş yapıyorsunuz acaba :d
@@adarozer nostalji oldu yorumu görünce :p yazılım firmasında proje yönetimindeyim -.- siz niye düştünüz buralara matematikçilik mi var
@@xc0437 Yok ben vize için çalışırken bu videoya bakmıştım öğrenciyim daha bilgisayar mühendisliği okuyorum. İşinizde başarılar.
@@adarozer ne güzel sizin için başarılı okul ve iş hayatı dilerim
You are my hero.
Hello!
I 'm still stuck in this algorithm. I just can't think of how to do the "merge" method. Does anyone may help me out?
There's a video on Merge Sort by Geeksforgeeks, watch it.
Imagine this great coder with great vision was not died in 2014, this was very unfortunate incidence for every code learner around the world
This person is awesome
Can someone explain to me this part
T(n)=2T(n/2)+C′.n
T(n)=2{2T(n/4)+C′.n/2}+C′.n
Why do we multiply by 2 here. And how does C′.n become 2C′.n
Also what is meant by the constant C here?
nC+C′.nlogn=θ(nlog n)
+ Praveen M
It is this,
first you have this equation.
T(n)=2T(n/2)+C′.n
so assume n-->n/2
then substitute n/2 to first equation
T(n/2)=2T(n/4)+C′.n/2
then again substitute above equation to the first equation T(n)=2T(n/2)+C′.n
Hope you got it now. :-)
Thank u brother
the proof is amazing
wait why do we reduce it to T(1)? 9:20
because in merge sort in worst case we need to divide the array until only 1 element is present in the array.
Unfortunately none of the time complexity maths makes any sense to me. Having said that, the algorithm implementation was definitely a great help! Im hoping that just knowing that it is O(nlogn) time complexity if good enough
No not always. To be a computer scientist/engineer you have to know deep down of a code.
Brilliant!
HI ,
Nice explanation,
could you please share the code with us,actually over internet mergesort() taking n parameters buts in ur case its only one and i like that very much.
Munni Saik There is a link in previous video to implementation, But anyway this is the code: gist.github.com/mycodeschool/9678029
well done
Nice explanation but @ 8:31, why are we having extra C`n outside? the expression inside the curly braces has already balanced the original equation
Because the outside C'n is from the original T(n) equation. The stuff inside the curly braces are the terms from the expansion of T(n/2).
If you look up some info about "recurrence relations", the expansion will make more sense. Hope that helps!
@@dee5392 thanks a lot for the clarification...finally understood 😊
@@arjundixit5913 you're welcome, glad I could help! have a great day :)
Thanks a lot for this nice video, but I don't understand how you get n/2k = 1, this is the only step that confuses me. Thanks!
to eventually reach T(1) ...as n=1(n
k=log n; 2^(log n) = n; n/n=1; T(n/n) = c;
For space complexity it is clear.
At level L1, there are n/2^1 elements, at level L2 there are n/2^2 elements....so on We know at last level there are 1 elements in array and we say it as n/2^k , then n/2^k =1
Nice explanation the noise in the background is a bit disturbing.
great video
Pls help getting infinite loop at merge (Larr)
Amazing