sir my doubt is in merge sort space total max function call a time is logn and each funciton call there will O(n) space so total should nlogn isnt it???
Sir doubt in merge sort space complexity
yes you are right
Merge Sort is quite fast, and has a time complexity of O(nlog n) .Time complexity of Merge Sort is O(nLog n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves.
no sir i m not talking about time complexity i am talking about space complexity
at a time each merge function will take O(n) space and at max there will logn fucntion call so space should be nlogn isnt it?
sorry my mistake of reading
No your are wrong for space complexity
you have make arrays in main function
and you are using same arrays and do all updation on same array
also while merging you are making new array but they are created every time
means when function called they will be created and when function completes they are destroyed
so your are using the space of the order n
hence space complexity =O(n)