Proof using strong induction for divide and conquer algorithm

Question

I've been working on an exercise that involves finding the min and max values of a set of integers using a divide and conquer algorithm. I'm specifically tasked with finding the number of comparisons that occur between integers for a given number of input values. I'm working through part c of the exercise:

I've solved parts a and b fairly easily using strong induction, but c gets weird. For context, I created an implementation of the algorithm for part c in Python which I know works correctly in giving me the number comparisons accurately, and from the pattern that emerges as the number of input values increases, I have found the following to be true for part c:

For an even number of inputs, the number of comparisons is $T(n) = \frac{3}{2}n-2$

For an odd number of inputs, the number of comparisons is $T(n) = \frac{3}{2}n-\frac{3}{2}$

My question is, how am I supposed to do prove these via strong induction? I know I need to account for both even and odd, but I'm not sure how to work that in. Does anyone have any advice?

Also, below is the Python code for those wishing to see/use it.

# Main recursive function for finding min/max
def min_max(L):
    # reference the global comparison counter instead of local copy
    global comp_counter

    # Store length of the array being handled
    length = len(L)

    # General case: Find the midpoint and split into two subarrays
    if length > 2:
        # For part c, split the list into n/2-1 and n/2+1 length subarrays if n!=2, is even, and is not divisible by 4
        if (length % 2 == 0) & (length % 4 != 0):
            split = (length // 2) - 1
            result = min_max(L[:split])
            result2 = min_max(L[split:])
        else:
            mid = length // 2
            # Call min_max() recursively twice with each half of the array
            result = min_max(L[:mid])
            result2 = min_max(L[mid:])

        comp_counter += 1
        # Store the minimum value between the two subarrays
        if (result2[0] < result[0]):
            result[0] = result2[0]
        comp_counter += 1
        # Store the maximum value between the two subarrays
        if (result2[1] > result[1]):
            result[1] = result2[1]
        # Return min and max in list format
        return result

    # Base Case: When the subarray is of length two, only one comparision is needed
    elif length == 2:
        comp_counter += 1
        # Implicit comparison, we are using Python's min/max functions to determine min and max
        # This could technically be done in one comparison, but from a mathematical perspective,
        # using the Python functions makes no difference.
        return [min(L), max(L)]

    # Base Case: When the subarray is of length one, it is both min and max, no comparisons needed.
    elif length == 1:
        return [L[0], L[0]]

    # If all else fails...
    else:
        return [float('inf'), -float('inf')]

if __name__ == '__main__':
    comp_counter = 0
    # Get input data and split by commas
    raw_data = input("Input numbers here ('x,y,z,...'): ")
    raw_data = list(raw_data.split(","))

    data = []
    # Take raw data and convert each element to type 'int' then store in 'data'
    for ele in raw_data:
        data.append(int(ele))

    # Compute Min/Max
    result = min_max(data)

    # Print output
    print("# of Elements: " + str(len(data)))
    print("Min: " + str(result[0]) + "; Max: " + str(result[1]))
    print("# of comparisons: " + str(comp_counter))
```

Answer 1

You have determined empirically, and want to prove use strong induction, that for the part (c) of the question the results are

$$T(n) = \begin{cases} \frac{3n}{2} - 2, & \text{if $n$ is even} \\ \frac{3(n - 1)}{2}, & \text{if $n$ is odd} \end{cases} \tag{1}\label{eq1A}$$

One important issue for proving \eqref{eq1A} is regarding the minimum number of values required initially to confirm as base cases. Since the original conditions only have different behavior for odd and even elements, and any special handling such as adding $2$ more comparisons when you split the group into $2$ only applies when $n \gt 2$ so it can be handled later, you only need to prove the base cases of $n = 1$ and $n = 2$.

1. For $n = 1$, no comparisons are needed. Since $T(1) = \frac{3(1 - 1)}{2} = 0$, this shows \eqref{eq1A} holds for this case.

2. For $n = 2$, you only need one comparison. Once again, \eqref{eq1A} works since $T(2) = \frac{3(2)}{2} - 2 = 3 - 2 = 1$.

The next consideration is handling the initial inductive step, i.e., where you assume that \eqref{eq1A} has been proven for all $n \le k$ for some integer $k \ge 2$. Note part (c) of the question says

Now suppose we modify the algorithm so that when $n$ is even, but not divisible by $4$, we split the set into a set of $n/2 - 1$ and a set of $n/2 + 1$ elements.

This shows the algorithm behavior, at least for even elements, depends on whether they are congruent (i.e., have a remainder) of $2$ modulo (i.e., when divided by) $4$ or $0$ modulo $4$. This implies the induction would need to account for at least those $2$ cases specifically. Although you could handle the odd cases on their own, I believe it'll be somewhat simpler & easier to handle all $4$ different remainders between $0$ and $3$, inclusive, when divided by $4$. As such, consider the next value and check its remainder when divided by $4$, as

$$n = k + 1 = 4m + r \tag{2}\label{eq2A}$$

for some integers $m \ge 0$ and $0 \le r \le 3$. To avoid repeating the same equation results several times, note that

$$T(2m) = \frac{3(2)}{2} - 2 = 3m - 2 \tag{3}\label{eq3A}$$

$$T(2m + 1) = \frac{3(2m + 1 - 1)}{2} = \frac{6m}{2} = 3m \tag{4}\label{eq4A}$$

$$T(2m + 2) = \frac{3(2m + 2)}{2} - 2 = (3m + 3) - 2 = 3m + 1 \tag{5}\label{eq5A}$$

Also, note each sub-group from the split of the $n$ items has a size $\le k$, so the previous strong induction assumption can be used to determine their individual values.

The $4$ cases for $r$ from \eqref{eq2A} are:

1. With $r = 0$, the input is split evenly into $2$ sub-groups of $2m$, with each one's # of comparisons given by \eqref{eq3A}. Since $2$ more are required for comparing the returned results, the total would be $2(3m - 2) + 2 = 6m - 2$. As \eqref{eq1A} gives $T(4m) = \frac{3(4m)}{2} - 2 = 6m - 2$, it matches what was expected.

2. With $r = 1$, the input is split into $\frac{4m}{2} = 2m$ and $\frac{4m + 2}{2} = 2m + 1$ sub-groups. You have \eqref{eq3A} and \eqref{eq4A} for these sub-groups, along with the $2$ extra at the end, giving a total of $(3m - 2) + 3m + 2 = 6m$. In this case, \eqref{eq1A} gives $T(4m + 1) = \frac{3(4m + 1 - 1)}{2} = \frac{12m}{2} = 6m$, so it once again matches.

3. With $r = 2$, since $n \gt 2$, as per the special case handling in part (c) of the question, the input is split into $\frac{4m + 2}{2} - 1 = 2m$ and $\frac{4m + 2}{2} + 1 = 2m + 2$ sub-groups. Using the results from \eqref{eq3A} and \eqref{eq5A}, plus $2$ more for the final comparisons, gives a total of $(3m - 2) + (3m + 1) + 2 = 6m + 1$. Using \eqref{eq1A} gives that $T(4m + 2) = \frac{3(4m + 2)}{2} - 2 = 3(2m + 1) - 2 = 6m + 1$, thus matching again.

4. With $r = 3$, the input is split into $\frac{4m + 2}{2} = 2m + 1$ and $\frac{4m+4}{2} = 2m + 2$ sub-groups. You have \eqref{eq4A} and \eqref{eq5A} for these sub-groups, along with the $2$ extra at the end, to get a total of $3m + (3m + 1) + 2 = 6m + 3$. In this case, \eqref{eq1A} gives $T(4m + 3) = \frac{3(4m + 3 - 1)}{2} = \frac{12m + 6}{2} = 6m + 3$, so it matches in this case also.

This shows that \eqref{eq1A} holds for all of the possible cases, finishing the inductive step that if \eqref{eq1A} applies for all $1 \le n \le k$, then it also applies to $n = k + 1$. In conclusion, by strong induction, you have that \eqref{eq1A} applies for all positive integers $n$.