0

I want to ask you how can I calculate big o for this loop?' the x++ is clearly O(1) right? I don't understand the i*2 part... I watched videos on YouTube but i can't solve this. I will be thankful if you guys can help me understand this.

for(int i{3} ; i<=n ; i*=2){
      x++;
   }
Hossein
  • 1
  • 1
  • 2
    `i = 3, 6, 12, 24, 48, ...` – Evg Sep 21 '20 at 15:18
  • 3
    Since `i` grows exponentially, the computational complexity of the loop is `O(log n)`. – Andreas Wenzel Sep 21 '20 at 15:21
  • let's say, you need x steps to reach n. So, the eq. becomes 3*2^x = n; 2^x = (n/3); so log_2(n/3) =x; for n=99, we can calculate, log_2(99/3) = log_2(33), which is >5 and <7, so we can say 6. we can also see the progression as 3,6,12,24,48,96. So big O is logarithmic and which it should never exceed and clearly it depends on the starting value of i. – quidstone Sep 21 '20 at 16:16

0 Answers0