Re: Which Algorithm is Faster?


eKo1 wrote:
I have a problem that asks:

We have a problem that can be solved by a direct (nonrecursive)
algorithm that operates in n^2 time. We also have a recursive algorithm
for this problem that takes n lg n operations to divide the input into
two equal pieces and lg n operations to combine the two solutions
together. Show whether the direct or recursive version is more
efficient.

I think I can safely assume that n is the size of the input. Let a(n)
be the number of operations required by the recursive algorithm.

a(1) = 0 and for n > 1,
a(n) = (n+1)lg n + 2 lg (n/2) if n is even, and
a(n) = (n+1)lg n + lg [(n+1)/2] + lg [(n-1)/2] if n is odd.

which seems to be O(n lg n) (at least, for n = 2^k, k > 0), so the
recursive algorithm is faster right? Or perhaps I'm overcomplicating.
Maybe the author of the problem meant to say that the recursive
algorithm takes (n + 1)lg n operations. What do you think?

That would be my guess, but ... The answer to the orignial problem
might depend on n (and hidden constants, if there are any).

--- Christopher Heckman

.