Computational complexity vs other complexities Complexities, such as time complexity, space complexity, communication complexity and sample complexity, are often used to analyze the performance of algorithms. As far as I know, time complexity and space complexity are collectively referred to as computational complexity.

Are there other common complexities in theoretical computer science? Is there any theory that can cover all these complexities?
I wouldn't call communication and sample complexities "common". Space and time complexities apply to all algorithms, but the other complexities only apply to certain classes of algorithms. Hence, only space and time complexities should be deemed "common" and thus no others deserve such description.

There isn't any theory that covers all these complexities.