ISRO2011-56

Question

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$?

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n^2)$
• D. $O(n^3)$

Comments

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)

‘’’’’’

Answer 1

 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})$ 

Comments

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.

---

No i dnt know the answer

---

ya it will be O(n^2   )