Problem 54 - Discrete Mathematics with Applications

Question

Let \(t\) be a function defined by $$ t(n)=\left\\{\begin{array}{ll} a & \text { if } n=1 \\ t(\lfloor n / 2\rfloor)+t(\lceil n / 2\rceil)+b n & \text { otherwise } \end{array}\right. $$ where \(a, b \in \mathbb{R}^{+} .\) (Such a function occurs in the analysis of merge sort.) Prove that \(t(n)\) is a non decreasing function; that is, \(t(n) \leq t(n+1)\) where \(n \geq 1\)

Step-by-Step Solution

Answer

In order to prove that the function \(t(n)\) is nondecreasing, we first analyzed the base case \(n=1\) and showed that \(t(1) \leq t(2)\). Then, we considered the case when \(n > 1\) and derived expressions for \(t(n)\) and \(t(n+1)\). By showing that either \(\lfloor n/2 \rfloor = \lfloor (n+1)/2 \rfloor\) or \(\lfloor n/2 \rfloor < \lfloor (n+1)/2 \rfloor\), and \(\lfloor n/2 \rfloor = \lfloor(n+1)/2 \rfloor\) or \(\lfloor n/2 \rfloor + 1 = \lfloor (n+1)/2 \rfloor\), we established that \(t(n) \leq t(n+1) - b < t(n+1)\) for \(n \geq 1\), proving that the function is nondecreasing.

Step 1: Analyze the function for the base case n=1

Let's consider the base case when \(n=1\). Note that the function is defined as: $$ t(1)=a $$ Now let's find the value of \(t(2)\): $$ t(2)=t(\lfloor 2/2 \rfloor) + t([ 2 / 2]) + 2b = t(1) + t(1) + 2b = 2a + 2b $$ Since \(a, b \in \mathbb{R}^{+}\), we have: $$ t(1) = a \leq 2a + 2b = t(2) $$

Step 2: Analyze the function for n > 1

Now let's consider the case when \(n > 1\) and find expressions for \(t(n)\) and \(t(n+1)\). The given function is: $$ t(n) = t(\lfloor n/2 \rfloor) + t(n/2\rfloor) + bn $$ Now, let's write the expression for \(t(n+1)\): $$ t(n+1) = t(\lfloor (n+1)/2 \rfloor) + t(\lfloor(n+1)/2\rfloor) + b(n+1) $$

Step 3: Compare \(t(n)\) and \(t(n+1)\) to show that the function is nondecreasing

Our goal is to prove that \(t(n) \leq t(n+1)\) to show that the function is nondecreasing. By the given function definitions, note that: 1. \(t(\lfloor n/2 \rfloor) \leq t(\lfloor (n+1)/2 \rfloor)\) since either \(\lfloor n/2 \rfloor = \lfloor (n+1)/2 \rfloor\) or \(\lfloor n/2 \rfloor < \lfloor (n+1)/2 \rfloor\). 2. \(t(\lfloor n/2 \rfloor) \leq t(\lfloor n/2 \rfloor + 1) = t(\lfloor(n+1)/2 \rfloor)\), since either \(\lfloor n/2 \rfloor = \lfloor(n+1)/2 \rfloor\) or \(\lfloor n/2 \rfloor + 1 = \lfloor (n+1)/2 \rfloor\). Using the above two observations: $$ t(n) = t(\lfloor n/2 \rfloor) + t(\lfloor n/2\rfloor) + bn \leq t(\lfloor (n+1)/2 \rfloor) + t(\lfloor (n+1)/2\rfloor) + bn = t(n+1) - b $$ Since \(b > 0\), we have: $$ t(n) \leq t(n+1) - b < t(n+1) $$ Therefore, the function \(t(n)\) is nondecreasing.

Key Concepts

Proof Strategy

Understanding the strategy behind mathematical proofs, particularly within the context of discrete mathematics, is fundamental for grasping the behavior of functions and algorithms. A proof strategy for demonstrating that a function is nondecreasing might involve, as in our exercise, a base case analysis followed by an inductive step. For the base case, you evaluate the simplest instance of the function, which is when the input, here represented by the variable 'n', is at its minimum valid value. In our example, the minimum value for 'n' is 1.

For the inductive step, you consider the function at a general case 'n' and compare it with the function at 'n+1' to establish the desired relationship. Establishing inequalities between these two cases often involves reasoning about the properties of the components of the function, such as floors, constants, and summations. Typically, in the analysis of recursive functions like the one presented here, ensuring that the function value does not decrease as the input increases verifies the nondecreasing property. The proof is then completed by demonstrating that these relationships hold true across all possible values of 'n'.

Discrete Mathematics

Discrete mathematics plays a vital role in understanding algorithms and functions within computer science. It deals with discrete elements that use distinct values, such as integers, graphs, and statements in logic. Discrete mathematics covers a wide array of topics, from set theory and probability to combinatorics and graph theory. In this exercise, we delve into the recursive nature of a function that is typically encountered in the analysis of algorithms like merge sort.

The study of discrete mathematics not only helps in creating more efficient algorithms but also in proving the characteristics of these algorithms mathematically, like establishing the nondecreasing nature of a function. This comprehension is essential for computer scientists and mathematicians to reason about the correctness and performance of algorithms.

Recursive Functions

Recursive functions are functions that call themselves with smaller input values to solve a problem. They break down a complex problem into simpler problems of the same type. The merge sort algorithm is a classic example of a recursive function - it divides the array to be sorted in two halves, recursively sorts the two halves, and finally merges the sorted halves together.

Recursive functions generally have a base case, which serves as an exit condition from the infinite loop of function calls. In our example function, the base case is defined for when 'n' equals 1. Understanding recursive functions requires careful attention to the function's behavior at its base case and how it progresses towards that base case via recursive calls. Implications of recursive function calls for 'n' and 'n+1', as shown in our textbook problem, are analyzed to establish the nondecreasing property of a function.

Merge Sort Analysis

Merge sort is a highly efficient, comparison-based, divide and conquer sorting algorithm which divides the original array into smaller subarrays until the subarrays are trivially sorted (with zero or one element). After dividing, it conquers the problem by merging the sorted subarrays to produce new sorted arrays.

The analysis of merge sort often involves understanding the recursion tree and the merge process. The recursion tree helps visualize the splitting process and the depth of recursive calls.

Time Complexity

Traditionally, the time complexity of merge sort is analyzed by solving the recurrence relation associated with the recursive division of the array. In the case of our textbook example, we see a function that provides a simplified model for the merge sort's behavior. Proving that this function is nondecreasing showcases the behavior of the merge sort algorithm where the total time taken doesn't decrease as we increase the number of elements to sort, which aligns with the intuitive understanding that sorting more elements should not take less time. This underpins why evaluating the nondecreasing nature of a function related to merge sort is informative in understanding this algorithm's scalability.