Assume that methods m1 and m2 are static void and compute the same result by processing an argument of type Object[]. Empirically we find that m1 -> T(N) = 100N and m2 -> T(N) = 10Nlog2N where the times are in microseconds. For what size inputs is it better to use m1 and m2? So I would use m1 for big numbers while I would use m2 for small numbers right? just checking the answers.
+6
A:
You're looking for the value of N > 0 such that 100N > 10N log2 N, so that's just an algebra problem. Divide both sides by 10N and you get 10 > log2 N, i.e., N < 2**10, i.e. N < 1024. Not that hard!-)
Alex Martelli
2009-10-17 18:32:09
+1
A:
Well, log2N is going to hit 10 when N is 1024, so according to the formulae you've given us, you would use the second one for N <= 1024 and the first for N >= 1024. (What you do "on the boundary" doesn't matter - they'll be equal.)
However, from a practical point of view you should quite possibly pick one and maintain just that one. Do you expect very large inputs, or lots of small inputs? Is this definitely a bottleneck in your code? Which is the simpler algorithm?
There's a lot more to deciding which algorithm is the best than just which is the fastest for a given input. I would rather maintain a simple algorithm which runs slightly slower than a fast but insanely complicated one.
Jon Skeet
2009-10-17 18:32:10
No, that's O(n log n) because that's the most significant complexity.
Jon Skeet
2009-10-17 18:35:18
As I replied to the comment you made in Alex's answer, yes that's right.
Jon Skeet
2009-10-17 19:04:21
A:
Look at this: http://www.wolframalpha.com/input/?i=plot+100*n+and+plot+10*n*log2(n)
I haven't figured out yet how to modify the scale though. In any case, for future reference.
jldupont
2009-10-17 18:37:15