How to show the running time of the following algorithm? The outer loop runs n times. The inner loop runs Math.floor(n/i) times. So it would be O(n*Math.floor(n/i)). I do not know how to transform that into a proper expression involving Big Oh and n. Maybe it could be first expressed as a sum:
sum(sum(n/j) from j=i to n by increment i) from 1 to n
for i = 1 to n:
    j = i
    while j ≤ n:
        A[j] = A[j] + 1
        j = j + i

Could you please indicate, apart from the actual running time of the algorithm, how to show the said running time?
 A: First, note that the answer cannot depend on $i$: $i$ is a dummy variable used as loop index (and so is $j$), so the answer can only depend on $n$.
The inner loop performs two atomic operations, namely
      A[j] = A[j] + 1

and 
      j = j + i

so each inner iteration has constant cost $2$ (or similar, depending on the model of computation): anyway, $c = \Theta(1)$. In the middle loop, the only cost (besides the inner loop) is
      j = i

which I will also assume has cost $1$.
The overall cost is therefore
$$
T(n) = \sum_{i=1}^n \left(1+\sum_{j=1}^{\left\lfloor \frac{n}{i} \right\rfloor} c\right)
$$
which can be computed as
$$\begin{align}
T(n) &= n +  \sum_{i=1}^n \sum_{j=1}^{\left\lfloor \frac{n}{i} \right\rfloor} c = n +  \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor c \\
&= n +  c \sum_{=1}^n \left(\frac{n}{i} + \varepsilon_i\right) \tag{$-1 < \varepsilon_i\leq 0$} \\
&= n +c\sum_{i=1}^n\varepsilon_i + cn \sum_{i=1}^n \frac{1}{i} \\
&= n + c A n + cnH_n \tag{$-1\leq A \leq 0$} \\
&= \Theta(n\log n).
\end{align}$$
(The exact asymptotic expression being $T(n) \displaystyle\operatorname*{\sim}_{n\to\infty} cn\ln n$, as the harmonic series satisfies $H_n \displaystyle\operatorname*{\sim}_{n\to\infty}  \ln n$.)
