Time Complexity Of the Algorithm

Question

Q.6 The time complexity of an algorithm T(n), where n is the input size, is given by—
  T(n)= T(n-1) + 1/n, if n>1
         = 1, otherwise.

The order of the algorithm is—

(a) log n
(c) n^2
(b) n
(d) n*n

Answer 1

Option a is right

Comments

what is option c,d (n2,nn)???

---

i think option (c) is n^2 and option (d) is n^n

Answer 2

 

$$ T(n) = T(n-1) + \frac{1}{n}   ---------(1)$$

$$T(n-1)=T(n-2) + \frac{1}{n-1}-------(2)$$

$$T(n-2)=T(n-3) + \frac{1}{n-2}-------(3)$$

$$\text{put  T(n-1)  from  equation 2 to  eq. 1 then result will be }$$

$$T(n) =T(n-2) + \frac{1}{n} + \frac{1}{n-1}-------(4)$$

$$\text{put  T(n-2)  from  equation 3 to  eq. 4 then result will be }$$

$$T(n) =T(n-3)+ \frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2}$$

$\text{Similarly we can write-->}$

$$T(n) =T(n-4) + \frac{1}{n-3}+\frac{1}{n-2}+\frac{1}{n-1}+\frac{1}{n} $$

$$ \implies T(n)=T(0)+\sum_{i=1}^{n}\frac{1}{i}=0+H_n, $$

where $H_n$ are the harmonic numbers.

$$H_n=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdot\cdot\cdot+\frac{1}{n}=log(n)$$

$$T(n)=\theta(log(n))$$