Complexity of recursive algorithm, that finds largest element in an array

Question

How to calculate complexity of ths recursive algorithm?

int findMax(int a[ ], int l, int r) 
{
    if (r – l == 1)
        return a[ l ];

    int m = ( l + r ) / 2;
    int u = findMax(a, l, m);
    int v = findMax(a, m, r);

    if (u > v)
        return u;
    else
        return v;
}

I'm not seeing how this is recursive nor what language you're using specified in the question. Can you add more details please? — CalebB
– CalebB, Commented Dec 19, 2014 at 14:16
How can you not see that it's recursive? Look at lines 4 and 5. Also, the language is C. — Gillespie
– Gillespie, Commented Dec 19, 2014 at 14:18
It's recursive because there is a call to findMax inside the findMax method. Language really doesn't matter that much. To describe the problem you can do it in a pseudocode if you like. — PiotrWolkowski
– PiotrWolkowski, Commented Dec 19, 2014 at 14:18

PiotrWolkowski · Accepted Answer · 2014-12-19 17:44:15Z

3

From the Master Theorem:

T(n) = a * T(n/b) + f(n)

Where:

a is number of sub-problems
f(n) is cost of operation outside the recursion; f(n) = O(n^c)
n/b size of the sub-problem

The idea behind this function is that you repeat the operation on the first half of items (T(n/2)) and on the second half of items (T(n/2)). You get the results and compare them (O(1)) so you have:

T(n) = 2 * T(n/2) + O(1)

So f(n) = O(1) and in terms of n value we get O(n⁰) - we need that to calculate c. So a = 2 and b = 2 and c = 0. From the Master Theorem (as correctly pointed out in comments) we end up with case where c < log_ba as log₂2 = 0. In this case the complexity of whole recursive call is O(n).

edited Dec 19, 2014 at 17:44

answered Dec 19, 2014 at 15:01

PiotrWolkowski

8,8007 gold badges53 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Complexity of recursive algorithm, that finds largest element in an array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related