I know that the algorithmic complexity of CNNs and other methods of deep learning can't be fully expressed in simple terms, like big oh complexity. That said, how would one go about comparing the efficiency/complexity of CNNs to standard machine learning methods (say decision trees, LDAs, Naive Bayes, etc.)? Deep learning methods are expensive, but how do we know how expensive they are comparatively?
One deep learning method can apply to multiple problems (for example computer vision, natural language processing etc), the performance of the method may be different depends on the problem that the method handles, but there is "popular dataset" that usually use by deep learning researchers to benchmark their method. Let say you have deep learning method, if you want to know how efficient your method for handwritten classification you can benchmark your method by classifying mnist dataset and compute its accuracy. If you want to compare the performance of your method with another method you can search on the internet another method that uses the same dataset for benchmark, here is an example