Research has shown that relying only on self-reports for diagnosing psychiatric disorders does not yield accurate results at all times. The advances of technology as well as artificial intelligence and other machine learning algorithms have allowed the introduction of point of care testing (POCT) including EEG characterization and correlations with possible psychopathology. Nonlinear methods of EEG analysis have significant advantages over linear methods. Empirical mode decomposition (EMD) is a reliable nonlinear method of EEG pre-processing. In this chapter, we compare two existing EEG complexity measures - Higuchi fractal dimension (HFD) and sample entropy (SE), with our newly proposed method using Higuchi fractal dimension from the Hilbert Huang transform (HFD-HHT). We present an example using the three complexity measures on a 2-minute EEG recorded from a healthy 20-year-old male after signal pre-processing. Furthermore, we showed the usefulness of these complexity measures in the classification of major depressive disorder (MDD) with healthy controls. Our study is in line with previous research and has shown an increase in HFD and SE values in the full, alpha and beta frequency bands suggestive of an increase in EEG irregularity. Moreover, the HFD-HHT values decreased in those three bands for majority of electrodes which is suggestive of a decrease in irregularity in the frequency-time domain. We conclude that all three complexity measures can be vital features useful for EEG analysis which could be incorporated in POCT systems.