Time Complexity of nested for loops

Question

Consider the following C function

int fun(int n) {
    int I, j;
    for(i=1; i<=n; i++) {
        for (j=1; j<n; j+=i) {
            printf(“%d %d”, I, j);
        }
    }
}

Time complexity of fun in terms of $Θ$ notation is

1. $Θ(n\sqrt{n})$
2. $Θ(n^2)$
3. $Θ(n \log ⁡n)$
4. $Θ(n^2 \log n)$

---

My attempt:

What I understood that outer loop run for $n$ time and inner loop is depend on value of $i$. So, inner loop can not run for $n$ time and it should be $\log n$ time. Option $(3)$ correct.

Somewhere, it explained as: Time complexity $(n-1)/1 +(n-1)/2 +(n-1)/3 +\dots +(n-1)/(n-1) +1 = n\log (n-1) - \log(n-1) = O(n\log n)$

Good, but how he calculated $(n-1)/1 +(n-1)/2 +(n-1)/3 +\dots +(n-1)/(n-1) +1?$

Can you explain it, please?

My question is: How he obtained the initial sum?

Answer 1

For the first iteration of the outer loop, $i = 1$ so the inner loop is:

        for (j=1; j<n; j+=1) {
            printf(“%d %d”, 1, j);
        }

which is a very simple loop which will execute $n - 1$ times hence the first term in the expression.

For the second iteration of the outer loop, $i = 2$ so the inner loop is:

        for (j=1; j<n; j+=2) {
            printf(“%d %d”, 2, j);
        }

which iterates over the odd numbers up to $n - 1$ hence $\frac{n - 1}{2}$ times and the second term.

. . .

For the final iteration of the outer loop, $i = n$ so the inner loop is:

        for (j=1; j<n; j+=n) {
            printf(“%d %d”, 1, j);
        }

which will only execute once hence the last term in the expression.

Actually, some of those counts are not exact but the errors are insignificant in an order calculation.

P.S.You are inconsistent about $i$ and $I$ in your code, both C and maths are case sensitive.

Answer 2

\begin{align} (n-1)/1 +(n-1)/2 +(n-1)/3 +\dots +(n-1)/(n-1) +1 &= (n-1) \left(\frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n} \right) \\ \end{align} which is $n$ times something. That "something" is the sum of the values of $\frac{1}{x}$ at all integers $1, \ldots, n$. And that sum is an upper sum for the integral of $f(x) = 1/x$. So the integral of that function -- which is $\log$ -- is less than or equal to that amount. So the sum you're looking for has $$ S = n(1 + \ldots \frac{1}{n}) \le n \int_1^{n+1} \frac{1}{x}~ dx = n( log(n+1) - \log(1) ) = n \log(n+1). $$

The actual claim made -- that you get $n \log(n-1) - \log(n-1)$ is simply not true, but it's a decent approximation.

Anyhow, what I've written shows that your expression is in fact in $O(n \log n)$.