# How are “Problem Complexity” and “Solution Complexity” different?

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?

## 1 Answer

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.

• 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. – dalgo Feb 18 '20 at 23:34