## Test your intuition: logarithmic time

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 $O(n)$ algorithm runs in one-tenth of a second. On the same input, an $O(n^2)$ algorithm takes one and a half weeks to run. Approximately how long would an $O(n \log n)$ algorithm take on the same input?

1. a few seconds?
2. a few minutes?
3. a few hours?
4. 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.

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in teaching and tagged , , , . Bookmark the permalink.

### 10 Responses to Test your intuition: logarithmic time

1. mp says:

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

• Brent says:

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

• mp says:

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.

• Ganesh Sittampalam says:

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.

• Brent says:

Right, good point. =)

2. mdibaiee says:

Is this the correct solution?

“`
n = 1.5week / 0.1s = 9072000
time = n * log(n) = 0.1 * log (9072000) = 2.3112989209604318
“`

• Brent says:

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

• mdibaiee says:

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

• phyl says:

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

• Brent says:

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?