Recursive algorithm complexity analysis

Question

I am trying to analyze the complexity of this algorithm but I am not sure if its recurrence equation is T (n / 2) + 2n, could you help me? size of v > 100

bool pareado(int v[], int left, int right) {
    bool b;
    if (left >= right)
        b = true;
    else {
        int m = (left + right) / 2;
        bool baux = (abs(contarPares(v, left, m) - contarPares(v, m + 1, right)) <= 1);
        if (baux == false)
            b = false;
        else
            b = pareado(v, left, m) && pareado(v, m + 1, right);
    }
    return b;
}

The function "contarPares" is this:

int contarPares(int v[], int i, int j) {
    int count = 0;
    for (int k = i; k <= j; k++) {
        if ((v[k] % 2) == 0)
            count++;
    }
    return count;
}

@AlexGuteniev The point is that iterator pairs would make this algorithm much clearer. So, having two std::array<int,N>::const_iterator objects would go a long way. Even two clearly named int const* parameters would be better. — bitmask
– bitmask, Commented Jul 17, 2020 at 15:03

Jesper Juhl · Accepted Answer · 2020-07-19 18:48:17Z

1

Your pareado function has complexity O(n) [ for n = right-left ] before recursing. Given that on each recursion step you partition your input range, and handle them separately, you still have to iterate over the entire range once (for any iteration depth) in the worst case.

How many recursion depths are there? In the worst case you must wait until contarPares returns 0 because it has no input left, i.e. its range is empty. Given that you always half your input range, this will take log(n) recursions.

Since each depth costs O(n) and you have O(log(n)) depths, you come down to a total of O(n*log(n)).

Of course depending on your input array, you may terminate much earlier, but you won't exceed the limit given above.

edited Jul 19, 2020 at 18:48

Jesper Juhl

32.2k4 gold badges55 silver badges80 bronze badges

answered Jul 17, 2020 at 14:49

bitmask

35.2k17 gold badges107 silver badges174 bronze badges

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

Collectives™ on Stack Overflow

Recursive algorithm complexity analysis

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