I am looking to find the recurrence relation (RR) of the fnA()
, but I am unsure how $n$ is to be represented.
(More specifically, I am trying to work out the asymptomatic running time of the function, so I am assuming I need to find the RR first; but if I am wrong and I don't need to find that out, please mention).
int fnA(int[] array, int low, int high) {
if (low >= high)
return array[low];
else {
int gap = floor((high - low) / 5);
return (fnA(array, low, low + 2 * gap) +
fnA(array, low + gap, low + 3 * gap) +
fnA(array, high - 2 * gap, high));
}
}
The probelm I am having is that I don't understand what is happening to $n$ in the recurrence relation. For example (not accurate to the given fucntion):
$T(n) = 2T(n/3) + T(n/2) + Θ(1)$
I am not looking for the answer per se, just how I should be going about problems like these.