0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

New contributor
Ekin is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

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.