CODEWITHSUNDEEP
algorithmtime-complexity
Sam
Sam

Reputation: 17

Computing of time complexity of recursive function

I've understood how to compute the time and space complexity of algorithms, and I found an interesting problem for training.

// count the occurrence of an element in an array
// list is already sorted
function count (list, item, start, end) {
    if (start > end) {
        return 0;
    }
    const mid = Math.floor((start + end) / 2);
    if (list[mid] < item) {
        return count(list, item, mid + 1, end);
    }
    if (list[mid] > item) {
        return count(list, item, start, mid - 1);
    }
    return count(list, item, start, mid - 1) + 1 + count(list, item, mid + 1, end);
}

The answer is O(n). I thought it should be something with a logarithm. Can somebody explain to me, why I'm wrong?

Upvotes: 0

Views: 70

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

If we have n items all equal to the target, and we're counting them one by one:

... + 1 + ...

that's O(n) counts/calls at least.

Upvotes: 1

zch
zch

Reputation: 15278

Consider the case where all elements of the list are equal to item. In this case you will only use first and last return. So you can write runtime of your algorithm for n = end - start as roughly:

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

Which solves to T(n) = O(n).

Upvotes: 1

Related Questions