# 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.
The text passage discusses the Big O notation of a nested loop algorithm and includes a detailed analysis of the number of iterations of the inner loop. It also contains a discussion in the comments about the number of iterations of the inner loop in terms of \( i \).
no_question

the passage does not contain a direct mathematical question that is explicitly stated as a question. instead, it provides a discussion and analysis of the complexity of a given piece of code. the comments section includes some back-and-forth, but they are more of a discussion rather than a formal question and answer.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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.
user
The text passage discusses the Big O notation of a nested loop algorithm and includes a detailed analysis of the number of iterations of the inner loop. It also contains a discussion in the comments about the number of iterations of the inner loop in terms of \( i \).

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question that is explicitly stated as a question. Instead, it provides a discussion and analysis of the complexity of a given piece of code. The comments section includes some back-and-forth, but they are more of a discussion rather than a formal question and answer.