How to find a recurrence relation for this recursive algorithm?

Question

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.

Answer 1

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.