-4

Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge portion of the algorithm to reduce complexity.

function mergeSort(unsortedArray)
{

  let midpoint = Math.floor(unsortedArray.length/2);

  if(unsortedArray.length == 1)
  {
    return unsortedArray;
  }

  let leftArray = mergeSort(unsortedArray.slice(0,midpoint));
  let rightArray = mergeSort(unsortedArray.slice(midpoint,unsortedArray.length));

}

I know for binary search tree which ignores half of the array in every iteration the answer would easily be arrived at as log2 n.

Now I would like to calculate the Worst Case Time Complexity for only the portion which splits the array into left half i.e. let leftArray = mergeSort(unsortedArray.slice(0,midpoint));

Even if the above code splits the array from index of 0 to midpoint. In the next level of recursion it would work on the entire array unlike Binary Search with index 0 to midpoint/2 going to left recursive call and index midpoint/2 to midpoint going to right recursive half.

So, How would we calculate Time complexity in a scenario where each level of recursion involves multiple recursive calls instead of one?

Brisingr
  • 1
  • 4
    Does this answer your question? [What is O(...) and how do I calculate it?](https://softwareengineering.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) – gnat May 17 '20 at 07:44
  • Hint: how many times does `slice` get called? – Caleth May 17 '20 at 08:51

1 Answers1

-1

The merge operation takes O(n) time complexity and since merging occurs logn times, the algorithm has a nlogn time complexity. With merge gone the divide algorithm would be of O(logn) complexity.

Rishav
  • 1