Why does this algorithm run in O(n log n)?

Question

We're supposed to "consider the following algorithm, which operates on an array A[1 . . n] of integers."

for i in [1 . . n] do
A[i] ← 0
for i in [1 . . n] do
    j ← i
    while j ≤ n do
        A[j] ← A[j] + 1
        j ← j + i

The assignment asks us to demonstrate that this algorithm runs in O(n log n).

The first loop is quite clearly going to add n to the run time, which would simply be dropped.

The second nested loops will run faster than a pure O(n^2) algorithm, since the while loop doesn't always run n times. When i = 1 it goes n times, i = 2 it will run n-1 times, all the way up to i = n where it will run once.

But, using the same method as Gauss summing the integers between 1 and 100, we can see that the while loop will run an average of (n+1)/2 times. Multiply by n for the for loop, and we get to (n^2 + n)/2, which can be simplified down to O(n^2), not O(n log n)

How does this result in an O(n log n) running time?

Your description of the running time of the while loop is incorrect -- it runs floor(n/i) times. So when i == 2 it will run floor(n/2) times, when i == 3, it will run floor(n/3) times. When i > n/2 (half the time) it will only run once. — Chris Dodd, Sep 23 '19 at 19:01

AugustinLopez · Accepted Answer · 2019-09-23T19:40:15.230

Considering the following:

for i in [1 . . n] do
    j ← i
    while j ≤ n do
        A[j] ← A[j] + 1
        j ← j + i

Each time, j is incremented with +i, not +1. As such, the first while loop while be iterated n times, then n/2, then n/3... up to n/n.

Ignoring integer rounding, we can write this in the following format: n(1 + 1/2 + 1/3 + ... + 1/n).

It seems that we are dealing with an harmonic serie, with an additional multiplication by n. Some more details here and here. This would be O(n log n).

Why does this algorithm run in O(n log n)?

1 Answers1