1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

There are various complexity measures including time, storage, amount of communication, number of gates in a circuit, number of processors and cache.

As @Laurentiu Cristofor mentioned, the most common ones are time and storage.

Computational complexity theory is a branch of theoretical computer science that covers this area.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.