8

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.

gnat
  • 21,442
  • 29
  • 112
  • 288
owwyess
  • 145
  • 1
  • 1
  • 8
  • how is this different from your prior question? [Asymptotic running time of for-loops](http://programmers.stackexchange.com/questions/253578/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. –  Aug 18 '14 at 16:32
  • base2 log is implied in the code, but logn 500 = 2.7 implies n = 10. The question I posed and the comment @KilianFoth made are making the same point, I just phrased it as a question not a statement – Caleth Aug 18 '14 at 22:25
  • What would this question's answer be good for? I would cry if i saw such a gross for loop in a codebase. – Alexander Aug 19 '14 at 04:28

2 Answers2

34

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)

Michael Borgwardt
  • 51,037
  • 13
  • 124
  • 176
  • 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
  • Put another way... integer division by two is a binary bit shift. 500 = 111110100, nine digits. – J... Aug 19 '14 at 09:03
8

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.

Community
  • 1
Boluc Papuccuoglu
  • 212
  • 2
  • 7
  • 2
    I always understood tilde to mean approximate, not proportional. Essentially, `~` is a shorthand for `≅`. – Davor Ždralo Aug 19 '14 at 07:12
  • 1
    *Proportional to* is the [`∝`](http://www.fileformat.info/info/unicode/char/221d/index.htm) symbol not `~`! The `~` is used to indicate equivalence relations or *approximate* equalities (see wikipedia's page about [tilde](http://en.wikipedia.org/wiki/Tilde#As_an_equivalence_operator)). – Bakuriu Aug 19 '14 at 08:26