4
for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j += i) {
       // some code
   }
}

The outer loop definitely runs n times. In case of the inner loop, assuming n = 8,

i j
1 1, 2, 3, 4, 5, 6, 7, 8 ---> ran N times
2 1, 3, 5, 7 ---> ran N/2 times
3 1, 4, 7
4 1, 5
5 1, 6
6 1, 7
7 1, 8
8 1

I am confused whether the complexity should be logn or n for the inner loop. Any help will be greatly appreciated!

InSync
  • 4,851
  • 4
  • 8
  • 30
nehacharya
  • 925
  • 1
  • 11
  • 31

1 Answers1

6

The outer loop iterates from i = 1 to n with a step size of 1. Therefore, the outer loop executes n times - linear time complexity.

The inner loop iterates from j = 1 to n with a step size of i. The step size i is dependent on the value of i in the outer loop.

As your table indicates;

  • When i is 1, the inner loop executes n times.
  • When i is 2, the inner loop executes n/2 times.
  • When i is 3, the inner loop executes n/3 times.
  • ...
  • When i is n, the inner loop executes n/n times, which is 1.

The sum of these iterations becomes:

n + n/2 + n/3 + ... + 1

If we factor out n, we obtain the harmonic series:

1 + 1/2 + 1/3 + ... 1/n

whose time complexity is approximated to log(n). You can see a more detailed explanation here https://stackoverflow.com/a/25905474/12974735

So, in total your code has O(n log(n)) time complexity.

Berthur
  • 4,300
  • 2
  • 14
  • 28
Sercan
  • 2,081
  • 2
  • 10
  • 23
  • 2
    Makes sense, thank you! – nehacharya Jul 12 '23 at 03:24
  • I ran an empirical experiment. I wrote a function hsum(n) which calculates the sum n + n/2 + n/3 + ... + n/n. And for i from 1 to 1000, I compared hsum(i) to i * log(i). The values are close and grow together. i log i is the smaller of the two, but the ratio between them slowly grows. It's around 0.92 at 1000, 0.9598952 at 1M, 0.9654264 at 10M. – Kaz Jul 12 '23 at 07:00
  • I think the total complexity is O(log(n)) not O(n.log(n)) as you don't process the data n times the harmonic series. The harmonic series already takes the 'i' loop into account. – Jérôme Radix Jul 12 '23 at 12:49
  • @JérômeRadix No, it would indeed be *O(n logn)* I think. The code would process *n + n/2 + n/3 + ... + 1* times, which is **not** the harmonic sum. The harmonic sum is *1 + 1/2 + 1/3 + ... + 1/n*, so we factor out *n* and then apply it back. This could be clarified in the answer, which leaves it a little ambiguous. – Berthur Jul 12 '23 at 12:58
  • @Berthur : thx, I understand now, but the answer says "The sum of these iterations is known as the harmonic series; n + n/2 + n/3 + ... + 1" which is wrong. – Jérôme Radix Jul 12 '23 at 13:02
  • 1
    @JérômeRadix Yes it is. Since the answer otherwise seems pretty good, I took the liberty to edit that part for clarity. – Berthur Jul 12 '23 at 13:09