NIELIT 2016 MAR Scientist B - Section C: 22

Question

Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by

$\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\  & =1, \text{ otherwise} \end{array}$

The order of this algorithm is

• A. $\log n$
• B. $n$
• C. $n^2$
• D. $n^n$

Comments

Using subsitution O(log n) therfore option A is correct

Answer 1

We can solve this by back substitution method.

T(n) = T(n-1)+1/n

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

T(n-2) = T(n-3) + 1/(n-2)

........

After moving like this, final equation we get as:

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

T(n) = logn

So A is the correct answer.

Answer 2

Using substitution method

O(Logn)