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.

About Brent

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.

  2. mdibaiee says:

    Is this the correct solution?

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s