CODEWITHSUNDEEP
javaalgorithmrecurrence
Navid Koochooloo
Navid Koochooloo

Reputation: 277

find recurrence equation of an algorithm java

I really don't know how to find the recurrence equation of an algorithm I've read the other questions about this subject but there are some stuff that I still don't get. for example in the following code (actually the pseudo-code :) ):

MergeSort(list "L" of "n" elements):
if n=<1 then return L
L1 <- MergeSort(L1... n/2)
L2 <- MergeSort(L(n/2 +1) ... n)
L <- Merge(L1, L2) 
return L

the recurrence equation is the following: T(1) = b T(n) = c1 + c2.n + 2T(n/2)

I don't get what is c1, c2 and b thanks for helping me

Upvotes: 1

Views: 819

Answers (1)

AllTooSir
AllTooSir

Reputation: 49372

Merge sort on n elements:

  1. If n = 1 , return the solitary element.
  2. Else , Recursively sort [1...n/2] elements and [n/2+1...n] elements.
  3. Merge the 2 sorted arrays.

Let the total time taken to merge-sort an array of n elements be T(n). As we know the base case is if the number of elements n is 1 , then we don't need to apply merge sort algorithm , we can just return that element . 

if n=<1 then return L

This will take a constant time , say c1.

If elements are greater than 1 then split the array from [1..n/2] and [n/2+1...n] and recursively merge-sort them.

L1 <- MergeSort(L1... n/2)
L2 <- MergeSort(L(n/2 +1) ... n)

So, as we assumed the time taken to merge-sort n elements is T(n) , then the time taken to sort each of the sub-array containing approximately n/2 elements will be T(n/2).

We need to merge the sub-arrays after sorting , time taken to merge n elements will be linear function of the n i.e. c2.n where c2 is the constant time taken to place an element in its specific position in the final sorted array.

Upvotes: 1

Related Questions