Recurrence Relation

Question

Let $T(n) = T(n-1) + \frac{1}{n} , T(1) = 1 ;$ then $T(n) = ? $

• A. $O(n^{2})$
• B. $O(logn)$
• C. $O(nlogn)$
• D. $O(n^{2}logn)$

Comments

If we use H.P. sum formula it will come as log(something). So by intuitively we can say option B is correct

---

yeah thanks

---

O(logn)

Answer 1

......

this is the way to dealing with such type of question 

 

 

 

 

 

 

Comments

O(logn) ....And I don't think that any one can explain more for this ...This is more than enough by the way wich part have you facing problem ????

---

Ok, your method is good, but

How you take the condition

where $n>1$ given in the question, you take $k =n-1$,right??

if $n>=1$ given the question, what we take $k =?$

if $n>=0$ given the question, what we take $k =?$

 

---

I also have same doubt . Unable to explain sorry bro ..!

Answer 2

T(n)=1/1+1/2+1/3+1/4+.......+1/n

T(n)= O(logn)