Question

Solve the following recurrences where T(1) = 1 D) T(n) = 2T(n/2) + n^2 F) T(n)...

Solve the following recurrences where T(1) = 1

D) T(n) = 2T(n/2) + n^2

F) T(n) = 2T(n-1) + n

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

Homework Answers

Answer #1 
T(n) = T(n/2) + n^2
    = T(n/4) + n^2/4 + n^2
    = T(n/8) + n^/16 + n^2/4 + n^2
    = T(n/16) + n^/64 + n^/16 + n^2/4 + n^2
    = 1 + ... + n^2/16 + n^2/4 + n^2
    = n^2 + n^2/4 + n^2/16 + ...
    = n^2(1+1/4+1/16+...)
    = O()


T(n) = 2T(n-1) + n
    = 2(2T(n-2)+(n-1)) + 1
    = 2^2T(n-2)+ 2(n-1) + 1
    = 2^3T(n-3)+ 4(n-2) + 2(n-1) + 1
    .....
    .....
    = 2^nT(n-n)+ ... + 2^2(n-2) + 2(n-1) + 1
    = 2^nT(0)+ ... + 2^2(n-2) + 2(n-1) + 1
    = 2^n+ ... + 2^2(n-2) + 2(n-1) + 1
    = 2^(n+1) - n - 2 
    = O()
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
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....
Solve the following recurrences  using the recursion tree method T(n) = 4 T(n/4) + n, where T(1)...
Solve the following recurrences  using the recursion tree method T(n) = 4 T(n/4) + n, where T(1) = 0
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 Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1
Solve the Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1
Master Theorem: Let T(n) = aT(n/b) + f(n) for some constants a ≥ 1, b >...
Master Theorem: Let T(n) = aT(n/b) + f(n) for some constants a ≥ 1, b > 1. (1). If f(n) = O(n logb a− ) for some constant > 0, then T(n) = Θ(n logb a ). (2). If f(n) = Θ(n logb a ), then T(n) = Θ(n logb a log n). (3). If f(n) = Ω(n logb a+ ) for some constant > 0, and af(n/b) ≤ cf(n) for some constant c < 1, for all large n,...
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
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
Solve the recurrence relation using the substitution method: 1. T(n) = T(n/2) + 2n, T(1) =...
Solve the recurrence relation using the substitution method: 1. T(n) = T(n/2) + 2n, T(1) = 1, n is a 2’s power 2. T(n) = 2T(n/2) + n^2, T(1) = 1, n is a 2’s power
Q1. What are the theta values for the recurrences given below in : (1) T(n) =...
Q1. What are the theta values for the recurrences given below in : (1) T(n) = T((8/10)n) + n (2) T(n)=5T(n/5) + n^2 (3) T(n) = T(n-2) +2n
Consider the function f (t)= (−1)n if n < t ≤ n + 1 and where...
Consider the function f (t)= (−1)n if n < t ≤ n + 1 and where n ∈ N denotes a non-negative integer. Calculate: a. f ( 1 ) b. f ( 11.5 ) c. f (sqrt(1000000000000000000000000000000000012+1)) d. limt-> infinityf2(t)
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT