text: # 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? Commented 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
  Commented 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
  Commented 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.