Register

How to remove recurrence relation when two or more are combined
closed

• closed by
228 views
0 votes
0 votes
closed as a duplicate of: complexity

What should be the approch to solve these relations?

Consider the recurrence relation T(n) = T(n–1) + T(n/2) + n.

Which of the following is a good tight upper bound on T(n)

(A) Θ(n2)
(B) Θ(n2 log n)
(C) Θ(2 (log n)2)
(D) Θ(n (log n)2)

• closed by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
rexritz asked Aug 13, 2023
301 views
How to solve the following recurrence relation? I get confused when decimals are used in the expression.
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
User Avatar
1 votes
1 votes
1 answer
2
iarnav asked Jul 29, 2017
2,489 views
How to solve this recurrence relation?
Given RR as - T(n) = 2T(n/2)+n ; n>1 T(1) = 1 Solve this using only BACK SUBSTITUTION method? Note - I am stuck at T(n)= 2^k.T(n/2^k)+(2^k-1).n and I'm putting 2^k=n Please help me I am getting wrong answer!
Given RR as -T(n) = 2T(n/2)+n ; n>1T(1) = 1Solve this using only BACK SUBSTITUTION method? Note - I am stuck at T(n)= 2^k.T(n/2^k)+(2^k-1).nand I'm putting 2^k=n Please h...
User Avatar
2 votes
2 votes
1 answer
3
indrajeet asked Feb 10, 2016
534 views
how to solve this recurrence relation
T(n) = 2*T(n/2) + n*logn please explain
T(n) = 2*T(n/2) + n*logn please explain
User Avatar
0 votes
0 votes
0 answers
4
radha gogia asked Jan 7, 2016
386 views
How to solve below recurrence relation ?
T(n)=2T(n-1)+n-1, T(1)=1 , n>=2 T(n)=2kT(n-k)+2(k-1)(n-(k-1))+2(k-2)(n-(k-2))+.......+n Now k=n-1 T(n)=2(n-1)(1)+2(n-2)(2)+2(n-3)(3)+.......+2(n-n)(n) T(n)=2(n)[ 1/1 + 2/2(2) +3/2 (3) + 2/ 2(4) +....] + n Now I am struck at this point how to proceed from here ?
T(n)=2T(n-1)+n-1, T(1)=1 , n>=2T(n)=2kT(n-k)+2(k-1)(n-(k-1))+2(k-2)(n-(k-2))+.......+nNow k=n-1T(n)=2(n-1)(1)+2(n-2)(2)+2(n-3)(3)+.......+2(n-n)(n)T(n)=2(n)[ 1/1 + 2/2(2)...
User Avatar
Link Copied!