I am analyzing some running times of different for-loops, and as I'm getting more knowledge, I'm curious to understand this problem which I have still yet to find out. I have this exercise called "How many stars are printed":

for (int i = N; i > 1; i = i/2) System.out.println("*");

The answers to pick from is A: ~log N B: ~N C: ~N log N D: ~0.5N^2

So the answer should be A and I agree to that, but on the other side.. Let's say N = 500 what would Log N then be? It would be 2.7. So what if we say that N=500 on our exercise above? That would most definitely print more han 2.7 stars? How is that related?

Because it makes sense to say that if the for-loop looked like this:

for (int i = 0; i < N; i++)

it would print N stars.

I hope to find an explanation for this here, maybe I'm interpreting all these things wrong and thinking about it in a bad way. Thanks in advance.

  • how is this different from your prior question? Asymptotic running time of for-loops
    – gnat
    Commented Aug 18, 2014 at 12:36
  • This has nothing to do with asymptotic running times.
    – owwyess
    Commented Aug 18, 2014 at 12:37
  • 1
    That option only makes sense if the base-2 logarithm is meant, not the base-10 logarithm. Commented Aug 18, 2014 at 12:39
  • 3
    What base are you assuming to get Log 500 = 2.7? and does that base appear anywhere in your code? N.b. you are only ever a constant factor different with logs of different bases
    – Caleth
    Commented Aug 18, 2014 at 12:44
  • 2
    @Caleth the logarithm base does appear in the code: i = i/2 the base is two because the loop is reversing repeated multiplication by two.
    – user22815
    Commented Aug 18, 2014 at 16:32

2 Answers 2


You've overlooked the key characteristic of the logarithm base.

Because i is divided by 2 in each iteration, the running time is logarithmic with base 2. And

log2(500) ~ 8.9

What you are looking at is

log10(500) ~ 2.7

(logarithm with base 10)

By the way, the reason why the base is often omitted in runtime discussions (and your calculator probably doesn't have a button for log2) is that due to the mechanisms of logarithmic math, a different base corresponds to a constant factor and thus is not relevant when you're ignoring constant factors anyway. It can be calculated easily:

loga(x) = logb(x) / logb(a)

  • This makes total sense, so it's actually just my lack of knowledge about logarithms. Thanks for the simple and clear answer.
    – owwyess
    Commented Aug 18, 2014 at 12:41
  • Thanks @Michael Borgwardt. Any chance you could give the example above with N=500. How can I calculate that on a calculator with only log base 10?
    – owwyess
    Commented Aug 18, 2014 at 12:48
  • 2
    @owwyess you divide the log10 result by log10(2) Commented Aug 18, 2014 at 12:48
  • Sorry I had confused myself and divided with log10(10). Thanks all.
    – owwyess
    Commented Aug 18, 2014 at 12:49
  • 2
    The constant factor mentioned in the last paragraph is about 3.322 for base 2. I.e. you need ~3.3 digits of binary for one digit of decimal. Or if you rather, a 33 digit binary is ~10 digits in decimal. Commented Aug 18, 2014 at 13:46

In addition to Michael Borgwardt's answer, the tilde character in front of each answer should be read as "proportional to". So if you doubled N (say, from 500 to 1000), you would see that the run time (or, in this case, number of stars printed) would increase by a factor which would be equal to (log1000 / log 500), which is independent from which base you use.

  • 2
    I always understood tilde to mean approximate, not proportional. Essentially, ~ is a shorthand for . Commented Aug 19, 2014 at 7:12
  • 1
    Proportional to is the symbol not ~! The ~ is used to indicate equivalence relations or approximate equalities (see wikipedia's page about tilde).
    – Bakuriu
    Commented Aug 19, 2014 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.