# How do I work out the recurrence relation of the given function?

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.

## 1 Answer

In the following I won't pay much attention to floors, celings, and "off-by-one" errors since they won't ultimately matter in the analysis of the recurrence relation. However all of the following calculations can be made precise.

If $$n = \texttt{high} - \texttt{low}$$ then $$\texttt{gap} = n/5$$ and the algorithm will perform three recursive calls:

• The first on the $$2 \texttt{gap} = 2n/5$$ elements between $$\texttt{low}$$ and $$\texttt{low}+2\texttt{gap}$$.
• The second on the $$2 \texttt{gap} = 2n/5$$ elements between $$\texttt{low}+ \texttt{gap}$$ and $$\texttt{low}+3\texttt{gap}$$.
• The third on the $$2 \texttt{gap} = 2n/5$$ elements between $$\texttt{high}- 2 \texttt{gap}$$ and $$\texttt{high}$$.

Also notice that when $$n = O(1)$$ then the time complexity of the algorithm is constant, and that the time spent in the non-recursive parts of the algorithm is also $$O(1)$$.

The recurrence relation is then: $$T(n) = 3T\left( \frac{2}{5} n \right) + O(1),\\ \quad T(1)=O(1)$$

which can be solved...

using the Master theorem to yield $$T(n) = O(n^{\log_{5/2} 3}) = O(n^{1.1989\dots})$$.

• Thank you, Steven! This just made a whole lot of sense to me. The elements of the array was confusing me, but if you make the assumption 'if n=high−low...' things begin to work - something I didn't think of doing. And from this you can see that it's 3 calls of 2n/5. Again, thank you for the help :) – Jake Jackson Oct 21 '20 at 15:29