1
$\begingroup$

I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the difference between these two. Do you all have an example(s) that can help me to understand?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Problem complexity is the best we can achieve for a given problem (sometimes under given restrictions). We usually talk about problem complexity when dealing with lower-bounds and it means there is probably no algorithm with lower time/place complexity than the proved ones.

Algorithm complexity is on the other hand the resources needed for a specific algorithm to run. When some algorithm solves a given problem in time $t$, we know that this problem has at most time complexity $t$ and hence, the complexity of an algorithm is an upper-bound for the complexity of the problem it solves.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is very clear, thanks. "An algorithm is an upper-bound bound for the complexity of the problem it solves" wrapped it all together for me. $\endgroup$
    – dalgo
    Commented Feb 18, 2020 at 23:34

Your Answer

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

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