$\sum_{i=1}^n\frac{2n}{i} = O(n)$ How can you prove that $\sum_{i=1}^n\frac{n}{i}=O(n)$?  This looks somewhat like the harmonic series, so I would have thought that this should grow like $n\log n$ since the harmonic series grows logarithmically.  But it seems that in several places, when analyzing algorithms, computer scientists state that $O(n)$ is the growth rate, but I can't find a reference for why that is true.
About the only thing I can think of to try to prove it is to group the terms into the bottom half $\sum_{i=1}^{n/2}n/i$ and top half $\sum_{i=n/2+1}^n n/i$.  If we say that this is the function $f(n)$ then we've written
$$ f(n) = 2f(n/2) + \sum_{i=n/2+1}^n n/i $$
In the second term, we could perhaps estimate each term as 1/2 so that this shows $f(n)<2f(n/2)+n/2$.  But from my familiarity with the Master Theorem this looks bad.  In fact even if the second term had been constant, in the Master Theorem I think this is still indicating a greater than linear growth.
 A: You have to compute
$$
\sum_{i=1}^n \frac{n}{i} = n \sum_{i=1}^n \frac{1}{i} = nH_n,
$$
where $H_n$ is the $n$-th Harmonic number. The growth rate of the harmonic numbers is  known to be $\Theta(\ln n)$, so your sum is $\Theta(n\ln n)$.
See the cited Wiki article section on growth rate for a more precise estimate.
A: 
How can you prove that $\displaystyle \sum_{i=1}^n\frac{n}{i}=O(n)$?

It's not, it's asymtotic growth rate is $n \ln n$, due to the growth rate of the harmonic series.

But it seems that in several places, when analyzing algorithms, computer scientists state that $O(n)$ is the growth rate.

You have to distinguish between word-case complexity and average complexity which might be different.
Moreover, the growth rate is also in $O(n^{1+\varepsilon})$ for any $\varepsilon > 0$, which looks almost $n$-ish.
A: If $f(n) = O(g(n))$ then the limit definition is $$\limsup_{n \to \infty}\frac{|f(n)|}{g(n)} < \infty.$$
Then $|f(n)| = |\sum_{i=1}^n \frac{2n}{i}| = 2n\sum_{i=1}^n \frac{1}{i}$ and $g(n) = n$. Now $$\limsup_{n \to \infty}\frac{|f(n)|}{g(n)} = \limsup_{n \to \infty}\frac{2n\sum_{i=1}^n \frac{1}{i}}{n} = 2\limsup_{n\to \infty} \sum_{i=1}^n \frac{1}{i} = \infty$$ since it is the harmonic series. So it is not $O(n)$. In fact, $f(n) = O(n\log n)$.
