Decaf-Math
Decaf-Math

Reputation: 359

Counting the number of occurrences of an element in an array using recursion

I've been given the following prompt:

Create a recursive function that counts the number of times v occurs in the array A by dividing A into two subarrays each time.

What better way to approach this than using BinarySearch? I created the following function:

int count(int *A, int low, int high, int v) { if(low > high) return 0; int total = 0, mid = (low + high)/2; if(A[mid] == v) total++; return count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v); }

This works, so I don't need verification on this part.

We are not told if the array A is sorted or not, so that's why it's necessary to search both the left half and the right half of the array A. But I need to find the time complexity of the function that I've written. Here's what I've thought:

Any variable assignments are O(1), so the only parts we need to consider are count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v). Since we're dividing the array into 2 parts with a subproblem size of 2, I've created the following recurrence relation:

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

which we can use the Master Theorem to give us T(n) = O(n). My question: is my assumption that the variable assignments are constant with O(1) and that each part of the count function is T(n/2) valid?

The overall time complexity we get of O(n) makes sense because we have to check all n elements in the array.

Upvotes: 1

Views: 2715

Answers (1)

wookie919
wookie919

Reputation: 3134

Was tempted to write just "Yes" in the answer and aim for the shorted accepted answer ever!

But to provide more information, under the most commonly used computation model in Algorithm analysis, any operations involving log(n) bits are assumed to be performed in O(1) time. What this effectively means is that unless your array is extremely large (e.g. 2^n) or the values themselves are extremely large, you are safe to assume that all operations can be performed in O(1) time.

As for your analysis regarding T(n/2), there's nothing else to say other than yes, that is correct, because you are simply halving the length of the array in each recursive call.

Upvotes: 1

Related Questions