How to show the running time of the following algorithm?

Question

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?

Answer 1

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$.)