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?

Solutions

Expert Solution

venereology answered 1 year ago

Next > < Previous

Related Solutions

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.

Let A be an integer array of length n. Design a divide and conquer algorithm (description...

Let A be an integer array of length n. Design a divide and conquer algorithm (description and pseudo code) to find the index of an element of the minimum value in the array. If there are several such elements, your algorithm must return the index of the rightmost element. For instance, if A = {0,2,4,5,2,0,3,10}, then the algorithm should return 5, which is the index of the second 0.

Sample Execution : Recursive Euclidean Algorithm to calculate GCD Type a positive integer for...

Sample Execution : ** Recursive Euclidean Algorithm to calculate GCD ** Type a positive integer for A: -2 Sorry, you must enter a positive integer (>0). Please try again. ** Recursive Euclidean Algorithm to calculate GCD ** Type a positive integer for A: 35 Type a positive integer for B: 63 The GCD is 7 Write a MIPS assembly program that prompts the user for 2 positive integers (>0). Then it uses the Recursive Euclidean Algorithm to calculate GCD (the...

1. Prove or Disprove: If n is a nonnegative integer, then 5 | (24n + 39n)

1. Prove or Disprove: If n is a nonnegative integer, then 5 | (2*4n + 3*9n)

Develop a recursive algorithm that multiply two integer numbers x and y, where x is an...

Develop a recursive algorithm that multiply two integer numbers x and y, where x is an m-bit number and y is an n-bit number (10 points), and analyze the time complexity of this algorithm (10 points).

Write a RECURSIVE method that receives as a parameter an integer named n. The method will...

Write a RECURSIVE method that receives as a parameter an integer named n. The method will output n # of lines of stars. For example, the first line will have one star, the second line will have two stars, and so on. The line number n will have "n" number of ****** (stars) so if n is 3 it would print * ** *** The method must not have any loops!

Subjects