The project (an Arduino logic analyzer) sounds exciting. I agree with Graynomad that you could basically malloc as much memory as you can, less a hundred or so bytes for the stack (used when you call functions).
However 2000 or so bytes won't capture many data points, especially if you are recording changes and need to save the time along with each change (say, 4 bytes each change).
You can get external SPI-based RAM chips, that could give you a fair bit more.
Or another approach might be a CPLD (logic array) which might be able to simultaneously capture changes and write them to external RAM.
I already have a hardware logic analyser but wanted to do a simple 1 (or maybe 2) channel software only version so peoples on here wanting help decoding signals could maybe be instructed to download and run the analyser sketch and then post the results.
As most stuff to decode comes in small packets I'm hoping an event driven approach of only logging data when something changes instead of every x micro/milli seconds will allow me to capture and serial send at least 425+ changes without buffer overflow.