8 votes 8 votes Let $T(n)$ be defined by $T(1) =10$ and $T(n+1)=2n+T(n)$ for all integers $n \geq 1$. Which of the following represents the order of growth of $T(n)$ as a function of $n$? $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n^3)$ Algorithms isro2011 algorithms time-complexity recurrence-relation + – shivanisrivarshini asked May 31, 2016 shivanisrivarshini 11.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply Nagasaikanmatha commented Sep 9, 2021 reply Follow Share alternative way T(1)=10 GROWTH – T(2)=10+4 2-->4 T(3)=10+10 3-->10 T(4)=10+18 4-->18 T(5)=10+28 5-->28 T(6)=10+40 6-->40 GROWTH IS ALMOST O(n^2) ‘’’’’’ 0 votes 0 votes Please log in or register to add a comment.
Best answer 12 votes 12 votes Answer -: $C$ $T(n+1)=2n+T(n)$ $= 2n+2(n-1)+T(n-1)$ $ = 2n +2(n-1) + 2(n-2)+T(n-2) ......$ $ =2n+2(n-1) +2(n-2) ... 2(1)+T(1)$ $ =2(n+n-1+n-2 ..... 1)+T(1)$ $ = 2 \times \frac{n(n+1)}{2 }+10$ $ = O(n^{2})$ shivanisrivarshini answered May 31, 2016 • selected Apr 4, 2018 by sourav. shivanisrivarshini comment Share Follow See all 15 Comments See all 15 15 Comments reply ManojK commented May 31, 2016 i edited by ManojK May 31, 2016 reply Follow Share @shivani is T(n+1)=T(n) ? 0 votes 0 votes shivanisrivarshini commented May 31, 2016 i edited by shivanisrivarshini May 31, 2016 reply Follow Share no I didn't get u 0 votes 0 votes ManojK commented May 31, 2016 reply Follow Share Is this sol representing order of growth of T(n) or T(n+1) ? 0 votes 0 votes shivanisrivarshini commented May 31, 2016 reply Follow Share T(n+1) 0 votes 0 votes ManojK commented May 31, 2016 reply Follow Share qus is about order of growth of T(n) 0 votes 0 votes ManojK commented May 31, 2016 reply Follow Share are you getting my point or not ? 0 votes 0 votes shivanisrivarshini commented May 31, 2016 reply Follow Share T(n)=T(n-1)+2(n-1) ?? Can't we do with this ?? 1 votes 1 votes ManojK commented May 31, 2016 reply Follow Share might not but question is about T(n+1)=2n+T(n) ? Can,t u solve T(n)=T(n+1)-2n like this using same method ? 0 votes 0 votes srestha commented May 31, 2016 reply Follow Share @Manoj I think T(n)=T(n+1)-2n is not right 0 votes 0 votes ManojK commented May 31, 2016 reply Follow Share why ? 0 votes 0 votes srestha commented May 31, 2016 reply Follow Share because T(n+1)>T(n) and in recurrence relation we comes from large to sorter value by derivation here T(n+1) is greater, So, cannot derive it from T(n) if u have any link to contradict my logic plz provide it I think it is never possible 1 votes 1 votes shivanisrivarshini commented May 31, 2016 reply Follow Share we always try to move from larger value to smaller I mean T(n) ... T(1) if You consider T(n)=T(n+1)-2n then we are moving to larger T(n)=T(n+1) -2n =T(n+2)-2(n+1)-2n = ......... How could you move forward 0 votes 0 votes ManojK commented May 31, 2016 i edited by ManojK May 31, 2016 reply Follow Share Ok see alternative for this type qus T(1)=10 T(2)=2*1+10 =12 T(3)=2*3+12 =18 T(4)=2*4+18 =26 T(5)=2*5+26 =36 T(6)=2*6+36 =48 T(7)=2*7+48 =62 Which is nothing but T(n)=O(n^2). Do you know ans. 2 votes 2 votes shivanisrivarshini commented May 31, 2016 reply Follow Share No i dnt know the answer 0 votes 0 votes ManojK commented May 31, 2016 reply Follow Share ya it will be O(n^2 ) 1 votes 1 votes Please log in or register to add a comment.