Time complexity nested loop

Question

I'm having a hard time understanding algorithm analysis, especially the following example:

for (int i = 1; i < n^3; i = 2*i){
  for (int j = 6*n; j > 0; j = j-2){
  }
}

So my understanding of this is that the outer loop is O(nlogn) as i is multiplied by a constant amount, I'm unsure if the n^3 makes any difference or not.

The inner loop confuses me the most though. I think it's O(n) as j is decremented by a constant amount but I'm uncertain whether the 6*n and the j > 0 have any influence.

If i'm correct then this entire algorithm would be O(nlogn)? Uncertain how to express the time complexity T(n) of this though.

Any insights would be hugely appreciated.

Note that ^ is the XOR operator in most programming languages. — Gumbo
– Gumbo, Commented Aug 1, 2015 at 4:43

Nir Alfasi · Accepted Answer · 2015-08-01 04:57:40Z

3

The outer loop is not O(nlogn) - since i is multiplied in 2 every loop, it goes: 2, 4, 8, 16, 32... this means that it will take a log(n^3) steps for i to reach n^3 (the base of the log is 2).

More formal: O(log(n^3)) = O(3logn) = O(logn)

In the inner loop j is initialized to 6*n and goes down in steps of 2. This means that it'll take 6n/2 steps for j to reach zero.

More formal: O(6n/2) = O(3n) = O(n)

So the complexity of the code section is O(n) * O(logn) = O(nlogn)

edited Aug 1, 2015 at 4:57

answered Aug 1, 2015 at 4:43

Nir Alfasi

53.6k11 gold badges94 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

M0rty Over a year ago

Sorry, do you mind elaborating? Still a bit confused

Nir Alfasi Over a year ago

@Dan_JAVA_SQL can you be more specific: which step in the process is unclear ?

M0rty Over a year ago

The outer loop makes sense now, what would have to be different for the outer loop to be O(nlogn)? Why are you dividing 6n by 2? Thanks

Nir Alfasi Over a year ago

The only thing that is not covered is your question in the comment above: "what would have to be different for the outer loop to be O(nlogn)?". This question is a bit vague. I guess that if you'll run the outer loop inside another loop that takes n steps...

M0rty Over a year ago

Great this is all starting to make sense! the only thing I still don't quite get is "since i is multiplied in 2 every loop, it goes: 2, 4, 8, 16, 32... this means that it will take a log(n^3) steps for i to reach n^3" wont it take log(n^2) as it goes 2, 4 ,8...

|

Collectives™ on Stack Overflow

Time complexity nested loop

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related