Complexity of a iterative function

Question

I have the following loop and wanted to understand the time complexity ...

for i = 1; i <= n; i++
    for j = 1; j <= n; j++
        j = j * i
    }
}

Did you even try to find similar questions here before posting yours? — Aakash Verma, Jul 29 '17 at 18:37
I think in this case it is O(∞), because in the first iteration of the outer loop, `j` always gets reset to zero, so it *never* reaches `n` and there is an infinite loop. Maybe you made a typographical error? — meowgoesthedog, Jul 29 '17 at 18:37
Structural time complexity is O(n^2). But your case will lead to termination due to timeout. — Aakash Verma, Jul 29 '17 at 18:39
I have now modified the answer to start at 1. Thanks for pointing that out. — Praj, Jul 29 '17 at 18:46
Nested iterations usually create a very high complexity. In your case it's O(n²). However for more details on this topic consider the following answer: https://stackoverflow.com/a/526751/8387078 — TrojaA, Jul 29 '17 at 18:34

score 0 · Answer 1 · answered Jul 29 '17 at 18:39

0

These for loops will run infinitely as j = j * i will always return 0 value for j when i=0.

If you are initializing i=1 then the complexity of these two loops will be O(n2) as explained in other comments/answers as it is nested loop.

answered Jul 29 '17 at 18:39

Abhijeet Dhumal

score 0 · Accepted Answer · answered Jul 29 '17 at 18:43

0

Inner Loop results in "stack overflow"

j value will always be 0 as it is multiplied by i whose value is 0.

So complexity will be O(INFINITY) .

If i is initialized from 1 i.e i=1 then it would result in some output whose complexity will be O(NlogN)

answered Jul 29 '17 at 18:43

Viresh Mathad

can you justify why this would be NLogN. Just trying to learn and not challenge. – Praj Jul 29 '17 at 18:55
The variable in the inner loop is being multipled by a value "i" and incremented always which is constant for each iteration. So if there any loop variable is being multiplied/divided by a constant then it is considered as O(Log N) – Viresh Mathad Jul 29 '17 at 19:06

2 Answers2