Which Algorithm is Faster?

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?

.

Relevant Pages

  • Re: Self function
    ... recursive algorithm is possible. ... Is it because most languages suck at recursion (specially python, ... a tail-recursion into an iteration should be the compiler's job, ... An algorithm, any algorithm, should be written in the way that is easier to ...
    (comp.lang.python)
  • Re: Books on recursive programming?
    ... a recursive algorithm which some ... compiler translates to an iterative algorithm is not a recursive ...
    (comp.unix.programmer)
  • Re: How to factor using Python?
    ... Factorial algorithm is a very simple and common algorithm, ... one of the most basic of all recursive algorithm ... consider the gamma function as Mark Dickinson pointed out. ...
    (comp.lang.python)
  • Semi-new Compression Method Fully Implemented
    ... First lemme say by no means is this the worlds best, ... recursive algorithm that I know of. ... whats the business aspect of the next step? ...
    (comp.compression)
  • Re: no lcm in standard library?
    ... which are comparable to the AMD K6 architecture, branch misprediction ... mispredict penalties tilt the algorithm choice in favor of Euclid's ... This implements the binary GCD algorithm which removes the branch ... that it approximates the divide as a 1-bit accurate divide, ...
    (comp.lang.c)