What is the time complexity of the code below?

Question

sum =0;

            for (int i=1; i<n; i++) {

              for (int j=1; j< n/i; j++) {

                sum = sum +j;

              }

            }

In the above outer loop , The variable i runs from 1 to n, thus making complexity of outer loop as O(n). This explains the n part of O(n logn) complexity.

But for the outer part when we see then j runs from 1 to n/i, meaning whenever i is 1 , the complexity is n so i guess the inner time complexity should also be O(n).

Making the total time Complexity as O(n*n)=O(n^2).

Answer 1

This is what you can do using Sigma notation:

With H_{n-1} is the harmonic function:

Finding Big O of the Harmonic Series