Solving a summation of an average case analysis

73 Views Asked by At

I was going over some review material for my Algorithms class that I would eventually take during spring semester and came upon this summation equation. Its an average case analysis of an algorithm that finds Max and Min of an array. What I can't figure out is how the summation goes from the top to the harmonic series. It later uses the series to justify the $\theta$ ln n

$\sum_{i=2}^n (({1\over i}) \times 1 + {(i-1)\over i} \times 2)$
= $\sum_{i=2}^n (2-{1\over i})$
= $2(n-1) - \sum_{i=2}^n {1\over i}$
= $2n - 1 - \sum_{i=1}^n {1\over i}$

1

There are 1 best solutions below

0
On BEST ANSWER

Because $\frac{i-1}{i}\cdot 2 =(1-\frac1{i})\cdot 2 =2-\frac{2}{i} $.