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.
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
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 ×...
For each set of conditions below, give an example of a predicate P(n) defined on N...
For each set of conditions below, give an example of a predicate P(n) defined on N that satisfy those conditions (and justify your example), or explain why such a predicate cannot exist. (a) P(n) is True for n ≤ 5 and n = 8; False for all other natural numbers. (b) P(1) is False, and (∀k ≥ 1)(P(k) ⇒ P(k + 1)) is True. (c) P(1) and P(2) are True, but [(∀k ≥ 3)(P(k) ⇒ P(k + 1))] is False....
Determine the​ upper-tail critical value t Subscript alpha divided by 2tα/2 in each of the following...
Determine the​ upper-tail critical value t Subscript alpha divided by 2tα/2 in each of the following circumstances. a.a. 1 minus alpha equals 0.99 comma n equals 81−α=0.99, n=8 d.d. 1 minus alpha equals 0.99 comma n equals 591−α=0.99, n=59 b.b. 1 minus alpha equals 0.95 comma n equals 81−α=0.95, n=8 e.e. 1 minus alpha equals 0.90 comma n equals 531−α=0.90, n=53 c.c. 1 minus alpha equals 0.99 comma n equals 441−α=0.99, n=44?
Is there a set A ⊆ R with the following property? In each case give an...
Is there a set A ⊆ R with the following property? In each case give an example, or a rigorous proof that it does not exist. d) Every real number is both a lower and an upper bound for A. (e) A is non-empty and 2inf(A) < a < 1 sup(A) for every a ∈ A.2 (f) A is non-empty and (inf(A),sup(A)) ⊆ [a+ 1,b− 1] for some a,b ∈ A and n > 1000.
Assume that you have a sample of n 1 equals 5​, with the sample mean Upper...
Assume that you have a sample of n 1 equals 5​, with the sample mean Upper X overbar 1 equals 48​, and a sample standard deviation of Upper S 1 equals 6​, and you have an independent sample of n 2 equals 4 from another population with a sample mean of Upper X overbar 2 equals 30 and the sample standard deviation Upper S 2 equals 7. Assuming the population variances are​ equal, at the 0.01 level of​ significance, is...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT