Tutorial 5: Applying the Master Theorem

Today I will write about my thinking and problem-solving steps for question 1 of tutorial 5.

Question: A non-empty array A with integer entries has the property that no odd number occurs at a lower index than an even number. Devise a divide-and-conquer algorithm for nding the highest index of an even number element, or -1 if A has no elements that are even numbers. Use the Master Theorem to bound the asymptotic time complexity of your algorithm.

I start by parsing through the question to understand it:

If A has the property that no odd number occurs at a lower index than an even number, then all even numbers are gathered at the front of A, followed by all odd numbers.

I list some examples:

n = 1:  [3], [2]
n = 2: [4, 1], [1, 3], [6, 4]
n = 3: [2, 6, 5], [2, 6, 8], [5, 3, 7]
n = 4: [4, 3, 1, 7]

Now I reason about what the algorithm should roughly look like based on some scratch work with the examples.

If we do the question by brute force, we would simply be checking each element in the array until we reach an odd number. Then the index of the element before the first odd number is the one we want(*). The worse case for this approach is n, when we would have to check every element in the array.

Using the divide-and-conquer process:

We first have to divide the array into smaller pieces. I decide to divide it into two halves from the middle because for now, I don't see any reason to divide it into more than two pieces. Call the first half L1 and the second half L2.

Check the middle element.
(I): If it's odd, we know that all even numbers come before this element, so we recurse on L1.
(II): If it's even, we know that there could potentially be more even numbers in L2, so we recurse on L2.

Now I think about the base case. The least number of elements a non-empty array can have is 1. There are two cases for this array:

Case 1: the element is odd. Then we should return -1 since there are no even numbers in the array. But because we have to think about how the base case relates to recursion, instead of -1, generally we return the index of the element before the first odd number, as metioned above in (*).

Case 2: the element is even. Then we should return the element's index.

So in pseudo-code, we have:
(# A is a non-empty array, b is the beginning index, e is the end index)

evenIndex(A, b, e):                                   
    if b == e:
        if A[b] is odd:                        # case 1
            return b - 1
        else:                                         # case 2
            return b
    else: (b < e)
        mid = floor[(b + e) /2]
        if A[mid] is odd:
            return evenIndex(A, b, mid + 1)                   # corresponding to (I)
        else:
            return evenIndex(A, mid + 1, e)                   # corresponding to (II)

Everything other than the recursion takes constant time, so the tight bound for those parts is big-theta(1). The recursive part of the algorithm takes max{ T[floor(n/2)], T[ceiling(n/2)]}.

So T(n) = { 1                                   if n = 1
                    1 +  T[ceiling(n/2)]     if n > 1}

Then by Master Theorem,
a = 1, b = 2, d = 0.
So a = b^d.

Therefore T(n) = big-theta(log n).