Calculating time complexity of a code snippet

Question

I am trying to calculate the time complexity of the below code snippet

def func()
{
   for(i=1; i<=n; i++)
   {
      for(j=1; j<=n; j=j+i)
      {
          print("hello")
      }
   }
}

This is how I calculate - The first for loop for variable i executes for n times. The inner for loop is dependent on i, the variable j is incremented as follows: 1 + 2 + 3 + ... + k and a time would come when it becomes larger than n. So 1 + 2 + 3 + ... + k = Sum of k natural numbers = k(k + 1)/2.

k(k + 1)/2 = n

So for inner for loop time complexity is O(n^1/2)

The time complexity of entire function = time complexity of outer for * time complexity of inner for = O(n * n^1/2)

But actually, it's O(nlogn). Can anyone please explain how and what is wrong with the approach I have used?

Answer 1

@Countingstuff explains that

j is not incremented as you say. Consider when i = n / 2, then the inner for loop goes from j = 0 (suppose we start at 0 rather than 1), to j = n / 2 to j = n.

In general for a given i, the inner loop will have about n / i operations. Thus we have n/1 + n/2 + n/3 + ... + n/n operations or thereabouts. For a total of n(1 + 1/2 + 1/3 + ... + 1/n). The bracketed expression is the harmonic series which is well known to be approximated by log n plus a constant that is absorbed by Big-Oh notation, leaving us with O(n log n).

(@Countingstuff please post such an answer, as previously requested, and I will gladly delete this one.)

Answer 2

No, the inner loop isn’t O(sqrt(n)). For I=100, you get j = 1, 101, 201, 301 etc.

Take n = 1,000,000. How many iterations of the inner loop when I = 1000, 10000, 100000?

90% of the time you have I >= 100,000 and the inner loop iterates at most 10 times. Calculate the number of iterations of the inner loop depending on I, then sum this up. If you can’t do the sum, Google for “harmonic series”.

A simple way to do the sum:

I = 1, n iterations
I = 2..3, 2 times (n/2) iterations
I = 4..7, 4 times (n/4) iterations
….
I = 1024..2047, 1024 times (n/1024) iterations

So how many times are you doing n iterations?