Question

Use the substitution method to show that for the recurrence equation: T( 1 )=2 T( n...

Use the substitution method to show that for the recurrence equation:

T( 1 )=2

T( n )=T(n-1) + 4n

the solution is T( n )= Big Theta( n2 )

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

Homework Answers

Answer #1 
Given
T( 1 )=2
T( n )=T(n-1) + 4n

Solving through substitution method
T( n )= T(n-1) + 4n
      = T(n-2) + 4(n-1) + 4n
      = T(n-3) + 4(n-2) + 4(n-1) + 4n
      ......
      ......
      ......
      = T(n-(n-1)) + 4(2) + ... + 4(n-2) + 4(n-1) + 4n
      = T(1) + 4(2) + ... + 4(n-2) + 4(n-1) + 4n
      = 2 + 4(2) + ... + 4(n-2) + 4(n-1) + 4n
      = 4 + 4(2) + ... + 4(n-2) + 4(n-1) + 4n - 2
      = 4(1 + 2 + .... + (n-2) + (n-1) + n) - 2

  

Time complexity = (Largest term by removing constants)

     

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 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
Given T(n)= T(n-1) + 2*n, using the substitution method prove that its big O for T(n)...
Given T(n)= T(n-1) + 2*n, using the substitution method prove that its big O for T(n) is O(n^2). 1. You must provide full proof. 2. Determine the value or the range of C.
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 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.
Consider the recurrence relation T(1) = 0, T(n) = 25T(n/5) + 5n. (a) Use the Master...
Consider the recurrence relation T(1) = 0, T(n) = 25T(n/5) + 5n. (a) Use the Master Theorem to find the order of magnitude of T(n) (b) Use any of the various tools from class to find a closed-form formula for T(n), i.e. exactly solve the recurrence. (c) Verify your solution for n = 5 and n = 25.
give T(n)=T(n-1)+2^n use substituiton method prove that it’s big oh O(n^2)
give T(n)=T(n-1)+2^n use substituiton method prove that it’s big oh O(n^2)
Also write the time complexity Solve the non-linear recurrence equation using recurrence A(n) = 2A(n/2) +...
Also write the time complexity Solve the non-linear recurrence equation using recurrence A(n) = 2A(n/2) + n Solve the non-linear recurrence equation using Master’s theorem T (n) = 16T (n/4) + n
Given the recurrence equation below, find running time T(n). T(n) = 8T(n/2) + n3 log n4...
Given the recurrence equation below, find running time T(n). T(n) = 8T(n/2) + n3 log n4 T(n) = 2T(n1/2) + log n
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
Solve the following recurrence relation T(1) = c1 T(n) = 2*T(n/2) + c2
Solve the following recurrence relation T(1) = c1 T(n) = 2*T(n/2) + c2
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT