for(int i = 0; i < N; i = i+1)
for(int j = i; j > 0; j = j/2)
StdOut.print("*");
The following are the possible answers:
A) O(log N),
B) O(N),
C) O(N log N),
D) O(N^2)
I know that the answer is C), but we are confused of why that is.
Neither A, B, C nor D can be an answer to the question "How many stars are printed?" because none of them are actually numbers. However, if your actual question is "What's the stars-printed complexity of this code?", you need to just examine the two loops :-)
The outer loop runs N times so that's the easier bit. It's N.
The inner loop starts j at i (which averages out over all the outer loops to be about N / 2), and halves it for each iteration. So, if i was 1024, that would be about ten iterations. If 512, about nine, 256 about eight, and so on.
That's clearly a logarithm situation where the inner loop runs a number of times that is related to log2N.
And, since you're running one loop within the other, you multiply the individual complexities to get O(N log N) (we don't really use the logarithm base in complexity analysis).
