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

@shivani

is T(n+1)=T(n) ?

---

no I didn't get u

---

 Is this sol representing order of growth of T(n) or T(n+1) ?

---

T(n+1)

---

qus is about order of growth of T(n)

---

are you getting my point or not ?

---

T(n)=T(n-1)+2(n-1) ?? Can't we do with this ??

---

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 ?

---

@Manoj I think T(n)=T(n+1)-2n is not right

---

why ?

---

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

---

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

---

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   )

---

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