Problem 18 - Discrete Mathematics with Applications

Question

Let \(b_{n}\) denote the number of multiplications needed to compute \(n !\) using the recursive factorial algorithm in Example 5.1 Show that \(b_{n}=\mathbf{O}(n)\)

Step-by-Step Solution

Answer

We can express the number of multiplications required, \(b_n\), to compute n! using the recursive factorial algorithm as \(b_n = b_{n-1} + (n-1)\), with base case \(b_1 = 0\). Using induction, we can prove that \(b_n = O(n)\). The base case, \(b_1 = O(1)\), holds as 0 = O(1). Assuming that \(b_{n-1} = O(n-1)\) in the inductive step, we can show that \(b_n = O(n)\) as well. Thus, we conclude that \(b_n = O(n)\).

Step 1: Express b_n in terms of n and b_{n-1}

Let's first express b_n as the number of multiplications required to compute n!. We have: \[b_n = b_{n-1} + (n-1)\] Here, b_{n-1} is the number of multiplications needed to compute (n-1)! and (n-1) accounts for the additional multiplications needed to obtain n! from (n-1)!.

Step 2: Define base case, b_1

In order to prove the complexity, we need to define a base case for our recursive relation: \[b_1 = 0\] This means that there are no multiplications required to compute 1!.

Step 3: Compute b_n for n=2, n=3, and n=4

Using our recursive relation, let's calculate b_n for n=2, n=3, and n=4. For n=2: \[b_2 = b_{1} + (2-1) = 0 + 1 = 1\] For n=3: \[b_3 = b_{2} + (3-1) = 1 + 2 = 3\] For n=4: \[b_4 = b_{3} + (4-1) = 3 + 3 = 6\]

Step 4: Prove b_n = O(n) by induction

We can prove that b_n = O(n) by induction. Let's use the following two-step induction process: 1. (Base case) Show that b_1 = O(1). 2. (Inductive step) Assume that b_{n-1} = O(n-1) and show that b_n = O(n) under this assumption. (Base Case) We know that b_1 = 0 and O(1) = 1, since there is no multiplication involved in this case, we can claim that b_1 = O(1). (Inductive Step) Let's suppose that b_{n-1} is in O(n-1). Using our recursive relation, we can express b_n as follows: \[b_n = b_{n-1} + (n-1)\] According to our assumption, b_{n-1} = O(n-1), which means there exists a constant C such that: \[b_{n-1} \leq C(n-1)\] Adding (n-1) to both sides of the inequality, we get: \[b_n = b_{n-1}+(n-1) \leq C(n-1)+(n-1)\] Now, let's find a new constant k such that: \[k(n) = C(n-1)+(n-1)\] Let k = C + 1. Then, we can rewrite the inequality as: \[b_n \leq k(n)\] This shows that b_n = O(n), which proves our inductive step. Thus, by induction, we have proven that the number of multiplications needed to compute n! using the recursive factorial algorithm in Example 5.1 is b_n = O(n).

Key Concepts

Recursive Algorithm

A recursive algorithm is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. In a recursive approach, a function calls itself with a smaller input. This requires a base case to determine when to stop. Without a base case, the recursion would continue indefinitely.

For example, to calculate a factorial using a recursive algorithm, you might define the factorial of a number, denoted as \(n!\), as \(n \times (n-1)!\). Here, the function calls itself with \(n-1\) as the input until it reaches the base case where the factorial of 1 is 1: \(1! = 1\).

• Base Case: When the input is 1, return 1.
• Recursive Case: Multiply the number \(n\) by the result of the function called with \(n-1\).

This recursive structure simplifies complex computations by breaking them into manageable steps.

Mathematical Induction

Mathematical induction is a powerful technique used to prove a statement, theorem, or formula is true for every natural number. It involves two primary steps: the base case and the inductive step.

First, the base case involves proving that the statement is true for the initial value, often \(n=1\). This anchors the proof by showing it works for the beginning point of our series.

• Base Case: Verify the statement holds for \(n=1\).
• Inductive Hypothesis: Assume the statement is true for some arbitrary natural number \(k\).
• Inductive Step: Using the inductive hypothesis, prove the statement for \(k+1\).

This establishes that if the statement is true for one integer, it becomes true for the next, thus proving it for all integers in the series.

Factorial Computation

Factorial computation involves calculating the product of all positive integers up to a given number \(n\), symbolized as \(n!\). Factorials are crucial in various fields such as combinatorics, algebra, and calculus. Understanding how factorials grow quickly is key to solving many mathematical problems.

For example, \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\).

• Factorials grow very fast; hence, their computations can be resource-intensive.
• They are often involved in computations requiring permutations or combinations.

Factorials serve as the basis for recursive functions where each result is derived from previously computed values.

Big O Notation

Big O Notation is a mathematical notation used to describe the upper bound of an algorithm's complexity. It helps understand the worst-case scenario in terms of time or space as the input size grows.

This notation is crucial for assessing the performance and efficiency of algorithms, especially in contrasting different algorithmic approaches.

• It expresses the computational time of an algorithm as a function of the input size \(n\).
• "O(n)" means that the algorithm's performance will grow linearly with the input size.

In our example, proving \(b_n = O(n)\) means confirming that the time it takes to compute the factorial with our recursive algorithm scales linearly with \(n\), an insight into its efficiency.