0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – zfac122 Oct 21 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.