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 Aug 18 '14 at 12:36
  • This has nothing to do with asymptotic running times. – owwyess Aug 18 '14 at 12:37
  • 1
    That option only makes sense if the base-2 logarithm is meant, not the base-10 logarithm. – Kilian Foth Aug 18 '14 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 Aug 18 '14 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 Aug 18 '14 at 16:32

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)

|improve this answer|||||
  • This makes total sense, so it's actually just my lack of knowledge about logarithms. Thanks for the simple and clear answer. – owwyess Aug 18 '14 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 Aug 18 '14 at 12:48
  • 2
    @owwyess you divide the log10 result by log10(2) – ratchet freak Aug 18 '14 at 12:48
  • Sorry I had confused myself and divided with log10(10). Thanks all. – owwyess Aug 18 '14 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. – Captain Giraffe Aug 18 '14 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.

|improve this answer|||||
  • 2
    I always understood tilde to mean approximate, not proportional. Essentially, ~ is a shorthand for . – Davor Ždralo Aug 19 '14 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 Aug 19 '14 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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