retagged by
13,767 views
6 votes
6 votes
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) $\Theta (n^{2})$

(b) $\Theta (n^{2}\log n)$

(c) $\Theta (2^{(\log n)^{2}})$

(d) $\Theta (n^{(\log n)^{2}})$
retagged by

2 Answers

9 votes
9 votes

Lets Solve it by substitution. 

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

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

       = T(n-3) + T(n/8) + (n-2) + (n-1) + n

       = T(n-4) + T(n/16) + (n-3) + (n-2) + (n-1) + n

       = ------------

       = ------------

       = -------------

       = T(n-k) + T(n/(2^k)) + (n-(k-1)) + (n-(k-2)) + ------------------------------ + (n-2) + (n-1) + n 

       Now consider n = 2^k, then k = log n

       = T((2^k) - k) + T((2^k)/(2^k)) + (n - k + 1) + (n - k + 2) + ---------------------- + (n - 1) + n

       Now Put value of K

       = (2^(log n) - log n) + 1 + (n - log n + 1) + (n - log n + 2) + ------------------------ + n

       Here series {(n - log n + 1) + (n - log n + 2) + ---------------------- + (n - 1) + n} are in AP with (log n) element then 

       Hence Sn = ((log n)/2) *(n -log n + 1 + n) = O(n.log n)

Hence,

       T(n) = 2^(log n)

        From all the given answer, Option C is asymptotically close to T(n), Hence C will be the answer. 

0 votes
0 votes
let T(0)=0,T(1)=1

THEN T(2)=T1+T1+2=4;

           T(3)=T2+T(3/2)+3   (FOR WORST CASE CONSIDER 3/2=1.5= 2)

                 =T2+T2+3=4+4+3=11

          T4= T3+T2+4=11+4+4=19

          T5=T4+T3+5=19+11+5=35

          T6=35+11+6=52

           T7=52+19+7=78

         T8=78+19+8=105

NOW CHECK FOR 8 :OPTION B GIVES 182

                                  AND OPTION C GIVES 512 AND WE CAN OBSERVE THERE EXPONENTIAL RISE

SO OPTION B IS THE ANS

SO OPTION
Answer:

Related questions

1 votes
1 votes
2 answers
3
mdboi asked Oct 28, 2022
740 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
1 votes
1 votes
1 answer
4