0

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?

2
  • 1
    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 for my benefit), 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. n(1 + 1/2 + 1/3 + ... + 1/n) and the bracketed expression is the harmonic series which is well known to be approximated by logn May 28, 2021 at 1:03
  • @Countingstuff: if you would have posted that as an answer, the OP could accept it, which would make the issue on this site appear as solved.
    – Doc Brown
    May 29, 2021 at 6:34

2 Answers 2

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.)

0

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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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