3
$\begingroup$

I was wondering what is the correct time complexity expressed in terms of big O on this type of loop:

for(i=1;i<=n;i++)
    for(int j=1;j*i<=n;j++)
        // O(1) code here

The inner loops will make $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$. I know that this type of formula is $O(n \log n)$, so is this the correct time complexity on this piece of code?

$\endgroup$
5
$\begingroup$

$$n+\frac{n}{2}+\cdots +\frac{n}{n}$$

$$= n(1+\frac{1}{2}+\cdots +\frac{1}{n})$$

Now it is a well-known fact that $1+\frac{1}{2}+\cdots +\frac{1}{n} \le c \log n$, where $c$ is some constant.

$$\le cn(\log n)$$

So the overall Runtime is $\mathcal{O}{(n \log n)}$.

$\endgroup$
4
$\begingroup$

The number of times that the body of the inner loop runs is exactly $$ T(n) = \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor. $$ This is sequence A006218 in OEIS, where it is stated that $$ T(n) = n(\log n + 2\gamma - 1) + \tilde O(n^{131/416}). $$ The exact magnitude of the error term isn't known, but it cannot be reduced below $\tilde O(n^{1/4})$.

For more references, see the Wikipedia article on Dirichlet's divisor problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.