Writing a Discrete Fourier Transform program
When applied correctly, the DFT yields exactly the same result as convolution, it is no approximation (neglecting rounding errors due to limited precision of floating point calculations, of course).

To calculate the circular convolution of vectors $x$ and $y$ (both of length $N$):
$$
x \circledast y = \operatorname{IDFT}_N\left[\operatorname{DFT}_N[x]\cdot\operatorname{DFT}_N[y]\right]
$$
To calculate the linear convolution first append $N-1$ zeros to both vectors yielding the zero-padded vectors $\tilde x$ and $\tilde y$. Then:
$$
x * y = \operatorname{IDFT}_{2N-1}\left[\operatorname{DFT}_{2N-1}[\tilde x]\cdot\operatorname{DFT}_{2N-1}[\tilde y]\right]
$$

To implement the [I]DFT I highly recommend the FFTW library. I promise that it will take you less time to learn its usage than to write your own implementation. For the special case of $x$ and $y$ containing only $1$ and $0$ their might be a more efficient algorithm, though. You would have to look into the Cooley-Tukey algorithm that is used for the FFT and see if you can simplify it for your needs. Whether it gets simpler will also depend on how you define computational complexity - if you define it in terms of additions and multiplications a custom FFT implementation probably won't buy you much. But if you go down to the hardware implementation level you can save some multipliers in the first butterfly stage by replacing them with multiplexers. Anyway, it is well known that the FFT algorithm complexity is of order $N\log N$ as you say. I would like to think that you don't have to show this again.

If you'd like to play around with IFFT and FFT I recommend Octave (an open source Matlab clone).