1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What is your take on the number of iteration of the inner loop in terms of i? $\endgroup$
    – greybeard
    Jan 24 at 21:18
  • $\begingroup$ I am not sure. I was thinking the i is some representation n so at worst case i = n^6 $\endgroup$
    – Kuro
    Jan 24 at 21:20
  • 1
    $\begingroup$ 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) $\endgroup$
    – Kuro
    Jan 24 at 21:32

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.