How do I calculate the time complexity of a nested 'for' loop?

Question

Consider:

def fun(n):

    for i in range(1, n+1):
        for j in range(1, n, i):
            print (i, “,”, j)

I'm having trouble with the nested for loop. Is it 2n^2 + 2n + 1?

Possible duplicate of [Time complexity of nested for-loop](https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) — Celius Stingher, Sep 19 '19 at 18:26
@CeliusStngher: the above is not an entire duplicate, since here the step is `i`, not `1`. — Willem Van Onsem, Sep 19 '19 at 18:27

score 3 · Accepted Answer · answered Sep 19 '19 at 18:36

The inner loop runs from 1 (inclusive) to n (exclusive) in hops of i. That thus means that it will make (n-1)//i steps.

The outer loop makes n runs where i ranges from 1 to n. We can slighlty overestimate the total number of steps by calculating the number of steps as a sum:

 n                    n
---                  ---
\     n-1            \    1
/     ---    = n-1 * /   ---
---    i             ---  i
i=1                  i=1

We can here use the Stirling approximation: we know that the integral if 1/i will be between the sum of 1/(i+1) and 1/i.

The integral of 1/i, so we approximate this as:

 n         n
---        /\
\    1     |    1
/   ---  &approx; |   --- dx  = log(n) - log(1)
---  i    \/    x
i=1        1

So that means that the total number of steps is, in terms of big oh O(n log n).

score 2 · Answer 2 · answered Sep 19 '19 at 18:35

2

The complexity of your code is O(n log n). Inside the first for loop, the complexity is O(n/i) which in total we have:

O(n/1) + O(n/2) + ...+ O(n/i)+...+O(1)

Is equal to:

n O( 1 + 1/2 + ... + 1/n ) = n O(log(n)) = O(n log(n))

answered Sep 19 '19 at 18:35

aminrd

4,300
4
23
45

No it's not. The outer for loop is O(n). Isn't it? – aminrd Sep 19 '19 at 18:38
It is, times the inner loop O(n) because the step is 1 – Marat Sep 19 '19 at 18:39
2

O(n) happens only one time, it the very first iteration of the first loop. – aminrd Sep 19 '19 at 19:15

How do I calculate the time complexity of a nested 'for' loop?

2 Answers2