Here is a question to test your intuition for logarithms. **NO CALCULATORS** allowed, and don’t take a long time to work out an answer in your head! Just go with your gut. After you have committed to a choice (say, by writing it down), then go get a calculator and a pencil and see if you can work out whether you were right!

*On a certain input, an algorithm runs in one-tenth of a second. On the same input, an algorithm takes one and a half weeks to run. Approximately how long would an algorithm take on the same input?*

*a few seconds?*
*a few minutes?*
*a few hours?*
*a few days?*

I’m pretty sure it wasn’t until quite a few years out of undergrad that I would have gotten this right.

## About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Well, the correct answer is “What are the constant factors of these various algorithms?”, isn’t it?

No, it’s not supposed to be a trick question. Let’s say they all have a constant factor of 1 (or near enough that it makes no difference).

Yeah, this was more of “the pedantically correct answer”. The factor ratios would have to be immense to really matter. The correct correct answer is far more interesting. I got it right, but before going for the calculator I was only slightly convinced that I got it right.

Taking a logarithm also introduces a new constant factor (as you have to choose the base), but you’d have to make a pretty strange choice for it to make a difference to the answer.

Right, good point. =)

Is this the correct solution?

“`

n = 1.5week / 0.1s = 9072000

time = n * log(n) = 0.1 * log (9072000) = 2.3112989209604318

“`

Yep, that’s right! Did you have the right intuition?

Yep! I find your blog really interesting and insightful, thanks a lot!

Can you explain the different values of n here? I realize this is an intuition, just trying to follow. Thank you in advance.

Well, if Cn^2 = 1.5 weeks and Cn = 0.1s (assuming they have the same constant factor), we can divide Cn^2/Cn = 1.5w/0.1s to find n. Does that help?

I think the confusion was about “time = n * log(n) = 0.1 * log (9072000)”, where one n turns into 0.1 and the other turns into 9072000. It would be better expressed as “time = C * n * log(n) “.

Hmm I got this right but it felt plausible to me that the answer *could* have been minutes for a big enough n, but after doing the numbers it’s would have to be a hell of a large n, so that intuition was not quite right.

(still giving myself some points for the right answer, though!)