How to show the running time of the following algorithm? [closed]

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?

closed as unclear what you're asking by Silvia Ghinassi, jameselmore, yoknapatawpha, colormegone, ShaileshFeb 3 '16 at 2:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• The clarity of your Question would be improved if you separated the "code" from the summation above it. Perhaps you should rearrange the body of the Question to state the problem (including code snippet) and then give your ideas about finding or expressing the answer. – hardmath Feb 2 '16 at 20:23
• It seems to me that the inner loop runs $n-i+1$ times, actually. – user228113 Feb 3 '16 at 0:32

1 Answer

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

• Corrected the mistake (I had not seen $j$ was incremented by $i$, not $1$). – Clement C. Feb 2 '16 at 19:53
• Shouldn't $j$ start from $i$ as in the program? – Jack's wasted life Feb 2 '16 at 20:58
• @Jack'swastedlife I directly start from the fact that the inner loop is executed $\lfloor n/i\rfloor$ times. We have $j=(\ell+1)i$ for $\ell$ ranging from $1$ to $\lfloor n/i\rfloor$ (I should have used $\ell$ instead of $j$, possibly, for clarity). – Clement C. Feb 2 '16 at 20:58