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?

asked Feb 3, 2020 at 23:45
$\endgroup$

2 Answers 2

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.

answered Feb 4, 2020 at 0:23
$\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.

answered Feb 5, 2020 at 14:10
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.