Lempel-Ziv Complexity (LZC) has been demonstrated to be a powerful complexity measure in several biomedical applications. During sleep, it is still not clear how many samples are required to ensure robustness of its estimate when computed on beat-to-beat interval series (RR). The aims of this study were: i) evaluation of the number of necessary samples in different sleep stages for a reliable estimation of LZC; ii) evaluation of the LZC when considering inter-subject variability; and iii) comparison between LZC and Sample Entropy (SampEn). Both synthetic and real data were employed. In particular, synthetic RR signals were generated by means of AR models fitted on real data. The minimum number of samples required by LZC for having no changes in its average value, for both NREM and REM sleep periods, was 10(4) (p<;0.01) when using a binary quantization. However, LZC can be computed with N >1000 when a tolerance of 5% is considered satisfying. The influence of the inter-subject variability on the LZC was first assessed on model generated data confirming what found (>10(4); p<;0.01) for both NREM and REM stage. However, on real data, without differentiate between sleep stages, the minimum number of samples required was 1.8×10(4). The linear correlation between LZC and SampEn was computed on a synthetic dataset. We obtained a correlation higher than 0.75 (p<;0.01) when considering sleep stages separately, and higher than 0.90 (p<;0.01) when stages were not differentiated. Summarizing, we suggest to use LZC with the binary quantization and at least 1000 samples when a variation smaller than 5% is considered satisfying, or at least 10(4) for maximal accuracy. The use of more than 2 levels of quantization is not recommended.