a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based...

a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based on the formula 3n = 3n−1 + 3n−1 + 3n−1 b. Set up a recurrence relation for the number of additions made by the algorithm and solve it. c. Draw a tree of recursive calls for this algorithm and count the number of calls made by the algorithm. d. Is it a good algorithm for solving this problem?

Expert Solution

venereology answered 2 years ago

Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i...

Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i ← 1 to n do S ← S + i * i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try...

For any nonnegative integer n, let Y1 < Y2 < · · · < Y2n+1 be...

For any nonnegative integer n, let Y1 < Y2 < · · · < Y2n+1 be the ordered statistics of 2n + 1 independent observations from the uniform distribution on [−2, 2]. (i) Find the p.d.f. for Y1 and the Y2n+1. (ii) Calculate E(Yn+1). Use your intuition to justify your answer.

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based...

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based on the fact that xy = 2(x · (y/2)) when y is even and xy = 2(x · ⌊y/2⌋) + x when y is odd, together with the initial condition xy = 0 when y = 0.

Consider the following recursive algorithm for computing the sum of the first n squares: S(n) =...

Consider the following recursive algorithm for computing the sum of the first n squares: S(n) = 12 +22 +32 +...+n2 . Algorithm S(n) //Input: A positive integer n //Output: The sum of the first n squares if n = 1 return 1 else return S(n − 1) + n* n a. Set up and solve a recurrence relation for the number of times the algorithm’s basic operation is executed. b. How does this algorithm compare with the straightforward non-recursive algorithm...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns,...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns, as output, the sum of the first n positive odd integers. Your solution should be recursive, and it should not contain any "for" loops or "while" loops.

Given a positive integer n, write a recursive algorithm that returns the number of the digits...

Given a positive integer n, write a recursive algorithm that returns the number of the digits in n. For example, if the given number n is 12345, the algorithm should return 5. What is the time complexity of your algorithm? use java

Given a positive integer n, write a recursive algorithm that returns the number of the digits...

Given a positive integer n, write a recursive algorithm that returns the number of the digits in n. For example, if the given number n is 12345, the algorithm should return 5. What is the time complexity of your algorithm?

3. Consider the following recursive algorithm for computing the sum of the following series: S(n) =...

3. Consider the following recursive algorithm for computing the sum of the following series: S(n) = 1/1! + 2/2! + . . . + n/n!. ALGORITHM S (n) //Input: A positive integer n // Procedure: fact(n) returns the factorial of the number passed as parameter //Output: The sum of the series: S(n) = 1/1! + 2/2! + . . . + n/n! if n = 1 return 1 else return S(n − 1) + n/fact(n) Set up and solve a...

The factorial of a nonnegative integer n is written n! (Pronounced “n factorial”) and is defined...

The factorial of a nonnegative integer n is written n! (Pronounced “n factorial”) and is defined as follows: n! = n.(n-1). (n-2).……...1 (for values of n greater than 1) n!=1 (for n = 0 or 1) For instance, 5! = 5.4.3.2.1 which is 120. Write a Python program that reads a nonnegative integer n and calculates and prints its factorial. Your program should display a suitable error message if n entered as a negative integer. Figure 6. Exercise 6 ...

In mathematics, the notation n! represents the factorial of the nonnegative integer n. The factorial of...

In mathematics, the notation n! represents the factorial of the nonnegative integer n. The factorial of n is the product of non-negative numbers from 1 to n. Design a program that asks the user to enter a nonnegative integer and then displays the factorial of that number. Module main. Asks the user to enter a non-negative integer. A loop is used to require user input until a nonnegative number is entered. Once a nonnegative number is entered, the integer is...

Question

a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based...

Solutions

Expert Solution

Related Solutions

Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i...

For any nonnegative integer n, let Y1 < Y2 < · · · < Y2n+1 be...

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based...

Consider the following recursive algorithm for computing the sum of the first n squares: S(n) =...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns,...

Given a positive integer n, write a recursive algorithm that returns the number of the digits...

Given a positive integer n, write a recursive algorithm that returns the number of the digits...

3. Consider the following recursive algorithm for computing the sum of the following series: S(n) =...

The factorial of a nonnegative integer n is written n! (Pronounced “n factorial”) and is defined...

In mathematics, the notation n! represents the factorial of the nonnegative integer n. The factorial of...