ISRO CSE 2011 | Question: 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)

‘’’’’’

---

sometime till some n gives o(n'2)
after certain n it will start giving o(n)
and asymptotic analysis is for very large values

---

make it Tn=Tn-1+2n

---

Even if its trivial,
Just keep in mind that while solving recurrence problem we always need the reccurence to head to the base case
So, if we try T(n) = T(n+1) - 2n,
We see that the recurrence is going forward, toward larger and larger arguments.

So we have to work with the given recurrence,

Now T(n+1) = T(n) + 2n (Here it's growing downwards)
So using substitution we get T(n+1) = T(n-1) +2(n-1) + 2n
And solving the subsequent steps you get O(n^2) Link

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

No i dnt know the answer

---

ya it will be O(n^2   )

---

$T(n+1) = T(n)+2n ...Given$

Value of the next term $[T(n+1)]$  is value of current term $[T(n)]$  plus  $ 2n$
Thus, we can say

 If my next term is $n$, my current term becomes $n-1$
So we can write the equation as-

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

and now we can solve by usual substitution method.
 

PS: Its a minor change in question, but can be challenging in exam temperament.

Answer 2

If you observe:

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

It is a decreasing expression.

From the Master's Theorem:
a = 1, b = 1

=> O(n * f(n))  
=> O(n * 2n)  
=> O(n^2)

Comments

To apply Master's theorem you need to have/make a>= 1 and b>1. This is like explicitly mentioned in the definition

So, what you did is wrong.