Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
how is this different from your prior question? Asymptotic running time of for-loops –  gnat Aug 18 at 12:36
    
This has nothing to do with asymptotic running times. –  owwyess Aug 18 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 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 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. –  Snowman Aug 18 at 16:32

2 Answers 2

up vote 33 down vote accepted

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)

share|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 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 at 12:48
2  
@owwyess you divide the log10 result by log10(2) –  ratchet freak Aug 18 at 12:48
    
Sorry I had confused myself and divided with log10(10). Thanks all. –  owwyess Aug 18 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 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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