# single for-loop runtime explanation problem

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
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
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
@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. – Snowman 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)

-
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
@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
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.

-
I always understood tilde to mean approximate, not proportional. Essentially, `~` is a shorthand for `≅`. – Davor Ždralo Aug 19 '14 at 7:12
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