Question

Let T(n) = T(n/2) + log(n). Give matching upper and lower bounds for T(n): Using a...

Let T(n) = T(n/2) + log(n). Give matching upper and lower bounds for T(n):

Using a recursion tree

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

Homework Answers

Answer #1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The tree can be shown as

T(n)------log(n)

|

|

T(n/2)----log(n/2)

|

|

T(n/4)----log(n/4)

|

|

..

..

..

|

T(1)---log(1)

The depth of the tree is log2(n)

So,

Total operations added are

T(n)=log2(n)+log2(n/2)+log2(n/4)+......log2(n/2^d) where d is depth

So,

T(n)<=log2(n)+log2(n)+.....log2(n) (d times)

So,

T(n)<=d*log2(n)

So,

T(n)<=(log2(n))^2

Also,

T(n)>=log2(n/2)+log2(n/2)+log2(n/2)........d times

So,

T(n)>=d*log2(n/2)

So,

T(n)>=(log2(n))^2-log2(n)

So,

T(n)=Theta((log2(n))^2)

Kindly revert for any queries

Thanks.

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
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
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 this recurrence using recursion tree : 1)T(n)=T(n/2)+2^n 2)T(n)=16(n/4)+n
Solve this recurrence using recursion tree : 1)T(n)=T(n/2)+2^n 2)T(n)=16(n/4)+n
Draw a Recursion Tree and solve for the complexity of the following recursive function T(n) =...
Draw a Recursion Tree and solve for the complexity of the following recursive function T(n) = T(n/2) + log(n)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) =...
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 2T(n/3) + n Use the substitution method to verify your answer.
1a. Use the substitution method to prove that, if T(n) = T(n/3) + 5, then T(n)...
1a. Use the substitution method to prove that, if T(n) = T(n/3) + 5, then T(n) = O(log n). Hint: do not forget the inductive assumption. 1b. Given the recurrence T(n) = 2T(b √ nc) + n, determine the big-Θ height of its associated recursion tree. 1c. For the recurrence in part b, provide a mathematical formula for the total work that is performed at depth 4 of the associated recursion tree. Hint: the root has depth equal to zero.
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) =...
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 2T(n/3) + 2n. Use the substitution method to verify your answer.
Solve the following recurrence relation using the technique of unrolling T(n) <= 2*T(n/2) + n*log(n), given...
Solve the following recurrence relation using the technique of unrolling T(n) <= 2*T(n/2) + n*log(n), given T(n <= 2) = 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
Design a Full Recursion Tree: T(n) = 8T(n/2) + Theta(n^2)
Design a Full Recursion Tree: T(n) = 8T(n/2) + Theta(n^2)
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT