1

How many stars are printed? (Choose the smallest correct estimate.)

for (int i = 0; i < N / 2; i = i + 1)
    for (int j = 1; j < N / 2; j = 2 * j)
        StdOut.print("**");
  1. O(log N)
  2. O(N)
  3. O(N log N)
  4. O(N^2)

I'm kind of stuck with this question and I think it is A or D but im not sure.

I know how the Big O notation work but I'm more confused about the increment in the inner loop when you multiply by 2. The reason for me to think it is A is due to the outer loop being logarithmic(?)but as I said, I'm not so sure with the inner loop. Thank you in advance

Community
  • 1
  • 1
Kusra123
  • 21
  • 3
  • 5
    Why don't you simply retype the question in the image? (BTW: You should also add why you think it could be A or D) – FooTheBar Aug 20 '18 at 11:59
  • 5
    kindly consider adding the question in text format – Inder Aug 20 '18 at 12:02
  • 1
    [How to find time complexity of an algorithm.](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Bernhard Barker Aug 20 '18 at 12:05
  • I know how the Big O notation work but I'm confused about the increment in the inner loop when you multiply by 2. The reason for me to think it is A is due to the outer loop being logarithmic, but as I said, I'm not so sure with the inner loop Thank you in advance – Kusra123 Aug 20 '18 at 12:10
  • @Kusra123 your last comment should be in your question instead of being a comment. – aloisdg Aug 20 '18 at 12:11
  • Possible duplicate of [How many stars are printed?](https://stackoverflow.com/questions/51907299/how-many-stars-are-printed) – beaker Aug 20 '18 at 14:37

2 Answers2

4

Explanation

The outer loop generates N / 2 iterations. For each of this iteration, the inner loop goes up to N / 2, but in steps of 2 * j. That is, you reach N / 2 in log_2(N / 2) steps.

Example

Take the number 64. We start at 1 and multiply by 2 in each iteration:

 1
 2
 4
 8
16
32
64

We reached 64 in 6 steps. And, indeed, 64 is 2^6. So log_2(64) is 6.

Solution

So in total, you have N / 2 iterations from the outer loop, each generating log_2(N / 2) iterations of the inner loop. That makes

N / 2 * log_2(N / 2)

executions of the print line in total. Thus, 3. O(N log N) is the correct answer.

And, since it's big-O, the algorithm also runs in 4. O(N^2). However, 3. O(N log N) is the smallest correct estimate.

Zabuzard
  • 25,064
  • 8
  • 58
  • 82
  • Oh okay, that makes sense. In summary, could you say that the outer loop is a linear O(N) and the inner loop is logarithmic O(logN) which multiplied makes it linearithmic ? – Kusra123 Aug 20 '18 at 12:26
  • It's hard to view it that way, if you ask me. Maybe in this example, because the loops have no direct dependency of each other. All in all, you count the amount of times the `print` line is executed. The print line is inside the inner loop. The inner loop is inside the outer loop. – Zabuzard Aug 20 '18 at 12:29
  • Thanks for the explanation! – Kusra123 Aug 20 '18 at 12:34
1

I'm more confused about the increment in the inner loop when you multiply by 2 ...

When you start with 1 and keep multiplying a variable by 2, it'll take you log(N) (base 2) steps to reach N. Thus, the complexity of the inner loop is O(log(N/2) which is equivalent to O(log(N) - log 2) = O(log(N)).

The reason for me to think it is A is due to the outer loop being logarithmic ...

The outer loop on the other hand is O(N/2) = O(N) as i is increasing by 1 at every step and it'll take N/2 until i equals N/2.

Since, inner loop has no dependency on outer loop, we can multiply the complexities in this case and say that the overall complexity will be O(N*log(N)).

Thus, correct option is c.

Shubham
  • 2,847
  • 4
  • 24
  • 37