You are given N cents (integer N) Break up N cents into coins of 1 cent, 2 cent, 5 cents. Using a memoized algorithm, return the smallest number of coins needed to do this. (Ex: if your algorithm is called B, and N = 13, then B(N) B(13) returns 4, since 5+5+2+1 = 13 used the smallest number of coins. In contrast, 5+5+1+1+1 is not an optimal answer.) Draw the recursion tree for this. Derive complexity bound of algorithm, no proving needed just derive it by going through each component in the algorithm.

You are given N cents (integer N) Break up N cents into coins of 1 cent, 2 cent, 5 cents. Using a memoized algorithm, return the smallest number of coins needed to do this. (Ex: if your algorithm is called B, and N = 13, then B(N) B(13) returns 4, since 5+5+2+1 = 13 used the smallest number of coins. In contrast, 5+5+1+1+1 is not an optimal answer.) Draw the recursion tree for this. Derive complexity bound of algorithm, no proving needed just derive it by going through each component in the algorithm.

Similar questions

Describe the running time in terms of the variable n. it would be better to say That loop will run 2*n + 1 times instead of That loop will run O(n) times. public int mysterious(int n, int sum) { int i = 0; while (i < n) { i = i + 1; for (int k = 0; k < 25; k++) { sum = sum + i; } } return sum; }
Consider a variation of the Bucket Sort algorithm which uses an unknown number of buckets. We're given that the worst-case runtime of the algorithm is O(n.), Let the number of buckets be n* (n to the power of x). Fill in the following box with the proper numeric value of x such that the algorithm has the given runtime. For example, you could fill in 0, 1, 2, 3, 3.14 4.2, etc. Recall that we use Insertion Sort to sort each bucket. Answer:
Consider the following recurrence: T(1)=1; T(n) = 2.T()+n, for n> 1, n a power of 3. =..... Find T(27) by substitution, starting with n = 1, n = 65 2 169 29 15 6
I was told the answer is (n lg n) but I am not sure.
What is the running time of the following piece of code for a given integer n: x=2; while(x