Question

Give asymptotic upper and lower bounds for T .n/ in each of the following recurrences. Assume...

Give asymptotic upper and lower bounds for T .n/ in each of the following recurrences. Assume that T .n/ is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.

a) T(n) = T(n/2) +T(n/4)+T(n/8)+n

b) T(n) = T(n-1) +1/n

c) T(n)= T(n-1) +lg n

d) T(n) = T(n-2) +1/lgn

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

Homework Answers

Answer #1

a. T(n) = T(n/2) +T(n/4)+T(n/8)+n

Answer:

b. T(n) = T(n-1) +1/n

Answer:

c. T(n)= T(n-1) +lg n

Answer:

d. T(n) = T(n-2) +1/lgn

Answer:

Hope this answers your questions, please leave a upvote if you find this helpful.

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
Study guide practice problem: 1)Find and prove the tight asymptotic bounds (theta) for the following recurrence...
Study guide practice problem: 1)Find and prove the tight asymptotic bounds (theta) for the following recurrence equations. You can make an appropriate assumption for T(1), or T(0): a) T(n)=T(n-1)+3 b) T(n)=T(n/2)+1   
Use a recursive tree method to compute a tight asymptotic upper bound for recurrence function T(n)=...
Use a recursive tree method to compute a tight asymptotic upper bound for recurrence function T(n)= 3T(n/4)+n . then use substitution method to verify your answer.
Let H(n) = H(n/2) + log(n). Give matching upper and lower bounds for H(n) with the...
Let H(n) = H(n/2) + log(n). Give matching upper and lower bounds for H(n) with the following techniques: 1. Using a recursion tree 2. By substitution 3. Using the master theorem
Use Master Theorem to solve the following recurrences. Justify your answers. (1) T(n) = 3T(n/3) +...
Use Master Theorem to solve the following recurrences. Justify your answers. (1) T(n) = 3T(n/3) + n (2) T(n) = 8T(n/2) + n^2 (3) T(n) = 27T(n/3) + n^5 (4) T(n) = 25T(n/5) + 5n^2
Solve the following recurrences: (a) T(n) = T(n=2) + O(n), with T(1) = 1. Solve this...
Solve the following recurrences: (a) T(n) = T(n=2) + O(n), with T(1) = 1. Solve this two times: one with the substitution method and one with the master theorem from CLRS. When you use the master theorem, carefully show the values for the parameters a; b. For the following cases you can use your preferred method. In either case, show your work: (b) T(n) = 2T(n/2) + O(1), T(1) = 1. (c) T(n) = 3T(n/2) + O(1), T(1) = 1....
Does the Master theorem apply to the following recurrences. Justify your answer in each case. If...
Does the Master theorem apply to the following recurrences. Justify your answer in each case. If it applies, then also state the case and the solution. (a) T(n) = √ nT(n/2)+logn, (b) T(n) = T(n/2+ 31)+log n, (c) T(n) = T(n−1)+T(n/2)+n and (d) T(n) = T(n/7)+T(5n/13)+n.
Determine the p-value for each of the following situations. (Give your answer bounds exactly.) (a) Ha:...
Determine the p-value for each of the following situations. (Give your answer bounds exactly.) (a) Ha: β1 > 0, with n = 25 and t = 1.2 < p < (b) Ha: β1 ≠ 0, with n = 22, b1 = 0.22, and sb1 = 0.08 < p < (c) Ha: β1 < 0, with n = 22, b1 = -1.46, and sb1 = 0.79 < p <
Determine the p-value for each of the following situations. (Give your answer bounds exactly.) (a) Ha:...
Determine the p-value for each of the following situations. (Give your answer bounds exactly.) (a) Ha: β1 > 0, with n = 29 and t = 1.76 < p < (b) Ha: β1 ≠ 0, with n = 15, b1 = 0.23, and sb1 = 0.11 < p < (c) Ha: β1 < 0, with n = 25, b1 = -1.53, and sb1 = 0.71
Analysing Algorithmic Efficiency (Marks: 3) Analyze the following code fragment and provide an asymptotic (Θ) bound...
Analysing Algorithmic Efficiency (Marks: 3) Analyze the following code fragment and provide an asymptotic (Θ) bound on the running time as a function of n. You do not need to give a formal proof, but you should justify your answer. 1: foo ← 0 2: for i ← 0 to 2n 2 do 3: foo ← foo × 4 4: for j ← 1396 to 2020 do 5: for k ← 4i to 6i do 6: foo ← foo ×...
Use Fermat's method to factor each of the following N. Justify your answers. a. N=629 b....
Use Fermat's method to factor each of the following N. Justify your answers. a. N=629 b. N= 9208 c. N= 89208 d. N= (2^8+9)-1 Thank you in advance!
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT