Register

NIELIT 2016 MAR Scientist B - Section C: 22

• retagged by
1,438 views
1 votes
1 votes

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

  1. $\log n$
  2. $n$
  3. $n^2$
  4. $n^n$
• retagged by
User Avatar

2 Answers

2 votes
2 votes
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.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
11 answers
1
admin asked Mar 31, 2020
15,625 views
NIELIT 2016 MAR Scientist B - Section C: 12
Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$? Insertion sort. Merge sort. Quick sort. Bubble sort.
Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$?Insertion sort.Merge sort.Quick sort.Bubble sort.
User Avatar
0 votes
0 votes
2 answers
2
admin asked Mar 31, 2020
1,319 views
NIELIT 2016 MAR Scientist B - Section C: 17
A hash function $f$ defined as $f(\text{key})=\text{key mod }7$, with linear probing, insert the keys $37,38,72,48,98,11,56$ into a table indexed from $11$ will be stored in the location $3$ $4$ $5$ $6$
A hash function $f$ defined as $f(\text{key})=\text{key mod }7$, with linear probing, insert the keys $37,38,72,48,98,11,56$ into a table indexed from $11$ will be stored...
User Avatar
2 votes
2 votes
3 answers
3
admin asked Mar 31, 2020
1,353 views
NIELIT 2016 MAR Scientist B - Section C: 20
A hash table has space for $100$ records. Then the probability of collision before the table is $10\%$ full, is $0.45$ $0.5$ $0.3$ $0.34$ (approximately)
A hash table has space for $100$ records. Then the probability of collision before the table is $10\%$ full, is$0.45$$0.5$$0.3$$0.34$ (approximately)
User Avatar
8 votes
8 votes
10 answers
4
admin asked Mar 31, 2020
2,371 views
NIELIT 2016 MAR Scientist B - Section C: 1
Which of the following logic expression is incorrect? $1\oplus0=1$ $1\oplus1\oplus0=1$ $1\oplus1\oplus1=1$ $1\oplus1=0$
Which of the following logic expression is incorrect?$1\oplus0=1$$1\oplus1\oplus0=1$$1\oplus1\oplus1=1$$1\oplus1=0$
User Avatar
Link Copied!