# Calculating time complexity of a code snippet

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?

• 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. May 29, 2021 at 6:34

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

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?