Complexity: Number of MAC operations on a DSP
It appears to me that your analysis is basically correct, except that in the second case there are $\frac{N}{2}$ sums, not $N$ sums.

I'm not sure what you are looking for when you ask "how a DSP deals with complex numbers", but generally they are represented in one of two ways: as separate real and imaginary values, or as a "complex" entity (structure/object/whatever- depends on the language) that contains real and imaginary members.