Time complexity Big O Notation

Question

What is time complexity for this loop:
for(int i = 1; j<=n; i*=2)
{
System.out.println(“*”);
}

Answer 1

O(log n) assuming that j starts at 1 also. I'm not sure if using both j and i was a mistake. If j started at 0, you'd have an infinite loop.

The time complexity is proportional to the number of * that get printed there because printing * is one of the most frequently performed constant time steps in that algorithm. The number of * is roughly log base 2 of n if j starts at 1.

If you need help making sense of this, print out the values of j in your loop and set n to a value like 256. Compare that with log base 2 of n. I expect Math.log2(n) to be +-1 of the number of *.

If n and j are int, the data type range actually limits the number of steps to roughly 31 steps even if n was its maximum possible value of roughly 2 billion. If this was quite a trick question, O(1) could be argued based on these data type limitations.

Answer 2

Josh Greig Thank you! I just figured out. I made a mistake when I thought it was n/2. But actually “i” is a series of 2^n