Big O, Understanding when the increment is doubling

I am trying to find the Big O notation of this code below, really its the big theta, but whatever I believe its the same in this case.

for (i=2; i < n^2; i++){
for (j=3; j < 4i^3; j = 2*j){
x = i+n
}
}


One, I believe that the constant in 4i^3 can be dropped. And so, the inner loop is maybe, O(i^3) => (2^k)^3 for some summation of k = 0 to k = log (i^3). I am not really sure what to do from there. And, I'm not really sure if I understand that portion correctly.

• What is your take on the number of iteration of the inner loop in terms of i? Jan 24 at 21:18
• I am not sure. I was thinking the i is some representation n so at worst case i = n^6
– Kuro
Jan 24 at 21:20
• okay so lets say the inner loop, log i^3 base 2 because of the reasons stated in the question. Then, um since i=n^2 => i^3=n^6 then maybe O(log n^6)
– Kuro
Jan 24 at 21:32

The inner loop: After k iterations we have $$j = 3 \cdot 2^k$$. We exit the loop if $$3 \cdot 2^k \ge 4 \cdot i^3$$ or $$2^k \ge (4/3) \cdot i^3$$ or $$k \ge \log (4/3) + 3 \cdot \log i$$.
So we add $$\log (4/3) +3 \cdot \log i$$ for $$2 \le i \lt n^2$$. An immediate upper bound is $$n^2 \cdot (\log (4/3) + 6 \log n)$$. The actual number of iterations is not much smaller because for most values i, $$\log i \approx \log n^2$$. So we have roughly $$6 \cdot n^2 \cdot \log n$$ iterations of the inner loop.