Computing of time complexity of recursive function

Question

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?

Hint: consider the worst case. For which input would this method take longest? — Henry
– Henry, Commented Oct 11, 2020 at 11:30
Oh, exactly! If each element in array will be the same, then time complexity will be O(n). Thank you very much! — Sam
– Sam, Commented Oct 11, 2020 at 11:38

zch · Accepted Answer · 2020-10-11 11:33:32Z

1

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).

answered Oct 11, 2020 at 11:33

zch

15.4k3 gold badges43 silver badges50 bronze badges

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

2 Comments

Sam Over a year ago

I'm right that average time complexity will be O(log n)?

zch Over a year ago

@Sam, might be, depends on domain/distribution of inputs.

גלעד ברקן · Accepted Answer · 2020-10-11 11:34:26Z

1

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.

answered Oct 11, 2020 at 11:34

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Collectives™ on Stack Overflow

Computing of time complexity of recursive function

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related