This pilot study applied three distance-based bivariate Lempel-Ziv complexity (LZC) measures to investigate the changes in electroencephalogram (EEG) signals between 11 patients with Alzheimer’s disease (AD) and 11 age matched controls. These methods measure richness of complexity between pairs of signals. Complexity of control subjects’ EEGs was richer, i.e. signals were made from a greater number and greater range of subsequences, than those from AD patients in almost all cases in two non-normalized distance-based methods. Only some pairs including electrode T4 (2.1% of the total) occasionally showed the reverse result. Statistically significant differences were found with these two methods in 21 and 18 of 120 tested electrode pairs, respectively (Student’s t test, p<0.01). Receiver operating curves were used to calculate the sensitivity (number of correctly classified AD patients) and specificity (number of correctly classified controls). Accuracy is the combined correct classification of controls and AD patients. The maximum sensitivity found was 100%, specificity 90.9% and accuracy 86.4% at various electrode pairs with both non-normalized methods. The normalized method showed many electrode pairs with increased richness of complexity for AD patients than controls (67.5% of the total). It was found that this was due to the normalization procedure modifying the distribution of the original complexities from the electrode pairs. These findings suggest non-normalized distance-based bivariate LZC measures can be reliably applied to complex physiological signals such as human EEGs to further understand the effect of AD on the complexity of brain signals of patients. However, care must be taken when normalization procedures are applied.