CODEWITHSUNDEEP
algorithmbig-omaster-theorem
user8238012
user8238012

Reputation:

Find the value of f(n) in the master theorem

Firstly, let me say that i know the master theorem properties, so the problem is not here.

I need to know how to determine the values for the master theorem using an existing algorithm

So, I need to have T(n)=a*T(n/b) + f(n).

I know a is the number of recursive calls.

I know b is the division size of the problem

But I don't know how to determine what is f(n)

I got an example;

here we have a=2; b=2 f(n) = n

a=2 because we have 2 times the merge function call b=2 because of j=(k+i)/2

But I don't understand how we get f(n)=n

mergeSort(T,i,k)

Require T array

i,k integer so that Tm<=i<=k<=TM with Tm and TM the bounds of T

Ensure T is sorted between i and k

`if (k>i) then
    j=(k+i)/2;
    mergeSort(T,i,j);
    mergeSort(T,j+1,k);
    append(T,i,j,k);`

Thanks for your help.

Upvotes: 3

Views: 3437

Answers (1)

Patrick87
Patrick87

Reputation: 28292

In the Master Theorem, f(n) is the function which gives the non-recursive part of the recursive definition of the runtime. At each step of the recursive call, the algorithm will call itself some number of times and, optionally, do some extra work (all of this unless you're in a base case, in which case the work done is constant).

In Mergesort, f(n) = O(n) because the merging of two sorted sublists to produce a single sorted list containing all the sublists' elements takes linear time in the size of the combined sorted list.

In Binary Search, f(n) = O(1) because all that has to be performed at each step is a comparison of the target value to the value of the element in the middle of the sublist to be searched.

The way you can tell what f(n) is supposed to be is by taking all the recursive calls, moving the computation of any arguments outside of the function invocations, and then replacing the recursive function invocations with constant values. What remains is asymptotically the same as f(n).

Upvotes: 2

Related Questions