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?

$\endgroup$
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.

$\endgroup$
  • 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 Feb 18 '20 at 23:34

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.