CODEWITHSUNDEEP
algorithmbig-otime-complexity
Yeahia Md Arif
Yeahia Md Arif

Reputation: 7926

How to find out time complexity of mergesort implementation?

We all know that merge sorting algorithm time complexity is "N Log N". But from this below code how to calculate this "N Log N" big O notation step by step ? There are some answer about this question on internet but they are very complicated to understand. Please help me to understand. Million thanks in advance.

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}

I found this source code in this address:

http://www.cquestions.com/2011/07/merge-sort-program-in-c.html

Upvotes: 1

Views: 9031

Answers (5)

2cupsOfTech
2cupsOfTech

Reputation: 6073

Time Complexity of Merge Sort

If you know how to get recursive relation for merge sort then for time complexity the above explanation should suffice.

Upvotes: 4

Abdullah Babu Kalam
Abdullah Babu Kalam

Reputation: 519

Let's take this implementation of Merge Sort as an example

 void mergesort(Item a[], int l, int r) {
 if (r <= l) return;
 int m = (r+l)/2;
 mergesort(a, l, m);  ------------ (1)
 mergesort(a, m+1, r); ------------(2)
 merge(a, l, m, r);

a) The time complexity of this Merge Sort is O(nlg(n)). Will parallelizing (1) and (2) give any practical gain ? Theorotically, it appears that after parallelizing them also you would end up in O(nlg(n). But practically can we get any gains ?

b) Space complexity of this Merge Sort here is O(n). However, if I choose to perform in-place merge sort using linked lists (not sure if it can be done with arrays reasonably) will the space complexity become O(lg(n)), since you have to account for recursion stack frame size ? Can we treat O(lg(n)) as constant since it cannot be more than 64 ? I may have misunderstood this at couple of places. What exactly is the significance of 64 ?

c) http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html says merge sort requires constant space using linked lists. How ? Did they treat O(lg(n) constant ?

enter image description here

d) [Added to get more clarity] For space complexity calculation is it fair to assume the input array or list is already in memory ? When I do complexity calculations I always calculate the "Extra" space I will be needing besides the space already taken by input. Otherwise space complexity will always be O(n) or worse.

e) Lists only need some pointers changed during the merge process. That requires constant additional memory.

f) That's why in merge-sort complexity analysis people mention 'additional space requirement' or things like that. It's obvious that you have to store the elements somewhere, but it's always better to mention 'additional memory' to keep purists at bay.

Upvotes: 1

shapiro yaacov
shapiro yaacov

Reputation: 2346

Basically, taking from here, it is doing a merge (that takes O(n) time) and doing it O(lon n) times - since the array of numbers is cut in half each time.

Upvotes: 1

rasik141
rasik141

Reputation: 23

if You want to find the time complexity as an equation of T(n)= something, then assign values to every line. for example, every assignment statement gets 1unit (statements like these scanf("%d",&n); ) . the maximum number of times a loop runs is the time value for that loop.For example {for(i=0;i is less than n; i++} this line gets a value of n, because it loops through for n times. after adding every steps and values, you will get an equation of the form T(n)= n+something. The highest order term will be the Big O of the whole algorithm. for example you get a T(n)= n^3+n^2+700 , here n^3 is the highest order term, so the big O of the whole algorithm is n^3(n cube). it doesn't matter what the rest of T(n) is.

Upvotes: 0

amit
amit

Reputation: 178451

The function in the code denoted as mergeSort() takes O(n) time, it is looping constant number of times over the elements within range (low,high).

The function denoted as partition(), which is the actual sorting function, takes `O(nlogn) time. It can actually be denoted as:

T(n) = 2T(n/2) + C*n //for some constant C

Explanation:

Each recursive call to partition is T(n/2). There are two of them, so 2T(n/2). In addition, it calls mergeSort(), which is O(n), so we add C*n, for some CONSTANT C.

By master theorem case 2, with: c=log_2(2)=1, k=0, we get that the function is in Theta(n^c* log(n)^(k+1)) = Theta(nlogn).

tl;dr:
The sorting algorithm takes O(nlogn) time.

As a side note, the naming of the functions are really confusing.

partition(), which is the actual sorting algorithm should be named mergeSort(), and the currently mergeSort() function is just merging the two subarrays, so it should be named merge(). This is pretty much how it is usually named, as you can see for example in wikipedia

Upvotes: 3

Related Questions