# How to find a recurrence relation for this recursive algorithm?

I am trying my hand on different algorithms and i pondered upon this code snippet that confused me:

findMax(arr[], i, n)
{
ππ (n == 1)
πππ‘π’ππ arr[i];

n1 = findMax(arr[], i,n β 2 );
n2 = findMax(arr[], i + (n β 2), n β n/2);

ππ(n1>= n2)
πππ‘π’ππ n1;
πππ π
πππ‘π’ππ n2;
}


From my point of view, for the first if statement, it is a constant, so T(1) = C. This is where I get confused, for the next recursive statement since it will call n/2 recursively, does this mean it will run recursively for n/2 times?

And for the next recursive statement, does it mean it will call (n-(n/2)) recursively?

I know that the subsequent if else statement will call in C time.

Does this mean my recursive relation is

$$T(n) = 2T(n/2) + C$$?

Thank you all for your time.

## 1 Answer

For the case $$n=1$$, you're right.

For the recursions, $$n/2$$ and $$n-n/2$$ are the inputs of the next-called functions, these are not the frequency of the calls. (Spoiler: This is in fact not the case if we divide $$n$$ in half every time! What are we then expected to get?)

Strictly speaking, we have

$$T(i,n)=T(i,n/2)+T(i+n/2,n-n/2)+C=T(i,n/2)+T(i+n/2, n/2)+C$$ if we assume that all return statements take equal time. From here we observe that $$T(n,i)$$ does not depend on $$i$$. A way to see this is to use that the base case does not depend on $$i$$.

More strictly speaking, we can replace all $$n/2$$ by $$\lfloor{n/2}\rfloor$$, as $$n$$ could be a non-power of 2. But I guess this was not what you were asking.