How did you find out free running sampling frequency is 9 kHz for UNO? Can you post a link here, please? I want to know where or how to find those infos. Also, I looked at arduino reference page, UNO has 16 MHz ceramic resonator. Why does it only sample at a max rate of 9kHz? Can you teach me how to figure it out?
Download datasheet AtMega328 from atmel.com look into ADC section, you will find all information
Why would you think sampling rate is not a problem? Even if I used UNO, it still isn't a problem or you meant that if I use mega, It won't be a problem anymore? It looks like mega has the same cpu speed as UNO, it does have a lot bigger memory. You think the memory is a problem, is it because I need to get better frequency resolutions?
Exactly, don't confuse ADC resolution (which is least of your worry, as low as 8-bit o'k), and FFT resolution, that defined as Freq. range / Bin numbers. Having 4 kHz sampling and / 512-fft = 8 Hz. Paradox is , you need to lower sampling rate, to get better resolution! (I mention this in musical note recognition post). Other parameter, increasing fft-size, isn't an option , except you have Due board.