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 
- 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.
blog :: Brent -> [String] 
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!)
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.”
Hah, indeed!
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.
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.