CODEWITHSUNDEEP
algorithmbig-otime-complexity
M0rty
M0rty

Reputation: 1075

Time complexity nested loop

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.

Upvotes: 1

Views: 1096

Answers (1)

Nir Alfasi
Nir Alfasi

Reputation: 53525

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)

Upvotes: 3

Related Questions