Question

Consider the following recursive algorithm. Algorithm Mystery(n) if n=1 then Execute Task A; // Requires Θ(1)...

Consider the following recursive algorithm.

Algorithm Mystery(n)

if n=1 then

Execute Task A; // Requires Θ(1) operations

else

Mystery(n/3);

Mystery(n/3);

Mystery(n/3);

Execute Task B;  //Requires 2n operations

end if


Let C(n) be the complexity of Mystery(n). Use the method of backward substitution

to determine C(n) in three steps.


a) Write the recurrence relation for C(n) including the initial condition.

b) Write at least two substitution steps for C(n) and identify the pattern.

c) Determine the complexity class of the algorithm in terms of Θ(·).

Hand written working out helps me plenty if possible but all good if not !

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Please give thumbs up if you like it

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n...
Consider the following recursive algorithm Algorithm S(n) if n==1 return 1 else return S(n-1) + n*n*n 1)What does this algorithm compute? 2) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. 3) How does this algorithm compare with the non-recusive algorithm for computing thius function in terms of time efficeincy and space effeciency?
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Design a recursive algorithm to compute 3^n based on the formula 3^n=3^(n−1) + 3^(n−1) + 3^(n−1)....
Design a recursive algorithm to compute 3^n based on the formula 3^n=3^(n−1) + 3^(n−1) + 3^(n−1). Also do the recurrence relation.
Consider the following recursive equation s(2n) = 2s(n) + 3; where n = 1, 2, 4,...
Consider the following recursive equation s(2n) = 2s(n) + 3; where n = 1, 2, 4, 8, 16, ... s(1) = 1 a. Calculate recursively s(8) b. Find an explicit formula for s(n) c. Use the formula of part b to calculate s(1), s(2), s(4), and s(8) d Use the formula of part b to prove the recurrence equation s(2n) = 2s(n) + 3
Solve the following recurrences(not in Θ format) using backward substitution. Please write all necessary steps. M(n)...
Solve the following recurrences(not in Θ format) using backward substitution. Please write all necessary steps. M(n) = M(n - 1) - 3 where M(0) = 1, M(n) = 2M(n-1) + 3 where M(0) = 3 M(n) = 4M(n-1) where M(1) = 2
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n ==...
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n == 0)    return 0; else    return n * f(n - 1); } A. 120 B. 60 C. 1 D. 0 10 points    QUESTION 2 Which of the following statements could describe the general (recursive) case of a recursive algorithm? In the following recursive function, which line(s) represent the general (recursive) case? void PrintIt(int n ) // line 1 { // line 2...
LANGUAGE IS C++ 1- A link based getEntry method requires how many steps to access the...
LANGUAGE IS C++ 1- A link based getEntry method requires how many steps to access the nth item in the list? a)n b)n+1 c)n^2 d)n-1 2- When calling the insert or remove methods, what is an disadvantage for the link-based implementation of the ADT List? a)harder to understand b)must shift data c)searching for that position is slower d)takes more memory 3-What is the last step in the insertion process for a linked implementation of the ADT List? a)Connect the new...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT