Electroencephalogram (EEG) signals have been widely used to analyze brain activities so as to diagnose certain brain-related diseases. They are usually recorded for a fairly long interval with adequate resolution, consequently requiring a considerable amount of memory space for storage and transmission. Recently compressed sensing (CS) has been proposed in order to effectively compress EEG signals. However, its performance is closely dependent on how a compression dictionary is built. Through our study, we notice that building the best fit over-complete Gabor dictionary plays an important role in this task. In this paper, we evaluate the effect of different time and frequency step sizes in building Gabor atoms on the performance of EEG signal compression using CS with three common EEG databases used by the research community. Taking the Normalized Mean Square Error (NMSE) as a performance metric, we present a quantitative study with an attempt to provide more insight on how to adopt CS in EEG signal compression.