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

Question

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.

Answer 1

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})$.