Question

How do you find the recurrence relation for an algorithm?

Can you explain how you get a, b and c for masters theorem?

T(n)= aT(n/b)+O(n^c)

Answer 1

lets take an example to find its recurrence relation.

MergeSort Algorithm
void merge(int a[],int temp[],int l,int m,int r){
   int temp_pos=l,size=r-l+1,left_end=m-1;
   while(l<=left_end&&m<=r){
       if(a[l]<a[m])temp[temp_pos++]=a[l++];
       else temp[temp_pos++]=a[m++];
   }
   while(l<=left_end)temp[temp_pos++]=a[l++];
   while(m<=r)temp[temp_pos++]=a[m++];
   for(int i=0;i<size;i++){
       a[r]=temp[r];
       r--;
   }
}

void mergesort(int a[],int temp[],int l,int r){
   if(l<r){
       int mid=l+(r-l)/2;
       mergesort(a,temp,l,mid);
       mergesort(a,temp,mid+1,r);
       merge(a,temp,l,mid+1,r);
   }
}

Here mergesort() function dividing array a[] into two equal parts and calling mergesort again with
these two parts of array
let n was size of original array now size of two subproblems is n/2.
And T(n) was total time for a problem for size n.
T(n) = T(n/2)+T(n/2) + f(n);
T(n) = 2*T(n/2) + f(n);
each mergesort() function also call merge function which runs equal to size of input array.
merge() function complexity is O(n).
f(n) = O(n)
Therefore T(n) = 2*T(n/2)+O(n)

According to master's Theorem
T(n)= aT(n/b)+O(n^c)
a=2;
b=2;
c=1;