What is the difference between the complexity of an algorithm and the complexity of a problem?

Asked

Viewed 87 times

0

I would like to know the difference between the complexity of an algorithm and the complexity of a problem, that is, which points differ the two things

computer-theory
  • 2

    I would advise you to take a look at the answer to this question : https://cs.stackexchange.com/questions/13669/what-is-the-difference-between-an-algorithm-a-language-and-a-problem and also look at this pdf : https://www.ime.usp.br/~Song/mac5710/slides/01complex.pdf

  • Usually, software complexity usually has to do with what the software does, how many responsibilities, things like that. See Zawinski’s law

1 answer

0

The correct terminology is to say that a problem belonging to a class time-consuming.

To know which class a problem belongs to, we must see which is the best algorithm that solves that problem (i.e., the algorithm with the shortest time complexity):

  • If this algorithm has polynomial complexity, the problem belongs to the class P;
  • If this algorithm has exponential complexity, the problem belongs to the EXPTIME class;
  • etc.

Browser other questions tagged computer-theory

You are not signed in. Login or sign up in order to post.