edited by
283 views
1 votes
1 votes

While going through some solutions of calculating algorithm complexity, i came across this statement

$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ........ + \frac{1}{n} = logn$

For example this is one question which came in GATE 2017 https://gateoverflow.in/118283/gate2017-2-38

I tried to prove it by mathematical induction, where P(n) = $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ........ + \frac{1}{n}$
Basis : P(1) = 1 and Log (1) = 0, even basis is not true.

Let me know what i am missing, and is this the correct expansion of log n

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
LavTheRawkstar asked Jan 12, 2017
808 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
3 votes
3 votes
2 answers
2
dhruba asked Jun 5, 2023
986 views
In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?a) Partition always divides the array into two non-empty subsets.b) ...
1 votes
1 votes
1 answer
3
sumitr asked Apr 10, 2019
1,263 views
What is the best case and worst case of the algorithm? And when will best case and worst case will happen??int main() { for(i=1 ; i<=n ; i++) { if(n%i == 0) { for(j=1 ; j...