Time Complexity of this nested loops

Question

what is the time complexity of this code? nlgn OR nlgn^2

for (int i = 1; i <= n ; i*=2 ) {
        for (int j = 1; j <= n ; j*=2 ) {
            for (int k = 0; k <= j ; k++) {
                x++; 
                      }}}

Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Carcigenicate, Feb 08 '17 at 19:19

score 0 · Accepted Answer · answered Feb 08 '17 at 19:29

0

First for takes log n time (exponential growth)

Second for loop also takes log n time(exponential growth)

Third one takes n time(linear growth)

So overall time = multiply all ,We get

log n * log n * n

So time complexity is

O(n (logn)^2)

answered Feb 08 '17 at 19:29

minigeek

2,766
1
25
35

score 0 · Answer 2 · answered Feb 08 '17 at 19:31

0

the time complexity for this will be n*((logn)^2) because the first loop will run for logn times the second will also run for logn times and the third loop will run for n times as it will be sum of gp 1+2+4+8. So the answer is n*(logn)*(logn)

answered Feb 08 '17 at 19:31

Anmol Saraswat

9
2

Time Complexity of this nested loops

2 Answers2