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.

16 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?

• Caleb says:

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

3. Ultra Bongo says:

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

4. sha says:

I recently had to work with an algorithm that runs in O(n log log n). The professor explained, “log log n grows very slowly. I just regard it as 5.”

• Brent says:

Hah, indeed!

5. martin says:

It’s a trick question.

The big O notation puts an upper bound on the rate of growth of a function: f = O(g) if, for all values of input greater than an arbitrary point in the domain and a constant scaling factor C, f(x) < Cg(x).

If all you know about an algorithm is that it is O(n log(n)), you would need a time of one input to know the maximum time of another input. The running times of unrelated algorithms tells you nothing.

Consider the following functions:

f( 2 ) takes 2 seconds
f( 4 ) takes 8 seconds
f( 8 ) takes 24 seconds

f'( 2 ) takes 2 minutes
f'( 4 ) takes 8 minutes
f'( 8 ) takes 24 minutes

f''( 2 ) takes 2 hours
f''( 4 ) takes 8 hours
f''( 8 ) takes 24 hours

f'''( 2 ) takes 2 days
f'''( 4 ) takes 8 days
f'''( 8 ) takes 24 days

f,f',f'',f''' are all O( n log(n) ), and can take seconds, minutes, hours, or days to complete for the same input.

• Brent says:

Yes, you’re absolutely right in theory, but it was not intended to be a trick question. Practically speaking, for “real-world” algorithms, the constant factors are similar enough that it does actually make sense to compare different algorithms like this.

This site uses Akismet to reduce spam. Learn how your comment data is processed.