Menu
I would like to know the difference between the complexity of an algorithm and the complexity of a problem, that is, which points differ from the two things
829
To summarize: A problem is a function or a mapping of inputs to outputs. An algorithm is a recipe for solving a problem whose steps are concrete and unambiguous. Algorithms must be correct, of finite length, and must terminate for all inputs.
The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
The complexity of an algorithm can be divided into two types. The time complexity and the space complexity.
The complexity can be found in any form such as constant, logarithmic, linear, n*log(n), quadratic, cubic, exponential, etc. It is nothing but the order of constant, logarithmic, linear and so on, the number of steps encountered for the completion of a particular algorithm.
Good question! Most people make no distinction between the two, which is a big no-no.
Simply put, the complexity of an algorithm is the algorithm's running time. This could be represented many ways, big O, big Theta, or any of the assorted Landau Notations. There also other representations, but the most commonly used in big O notation, which can be applied to analyze the worst-case time complexity of an algorithm as a function of the input size.
The complexity of a problem is typically the lower bound of any algorithm that solves the problem (wiki is a decent resource here). For example we can prove comparison-based sorting has a lower bound of n log n. This means, any algorithm that sorts by comparing elements, no matter which algorithm, will take at least n log n time in the worst case. Using Landau notation we would say this problem takes Omega(n log n).
In summary, problem complexity is a lower bound and algorithm typically establishes an upper bound. When you find an algorithm whose upper bound matches a problem's lower bound, you've found an asymptotically optimal algorithm!
134
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
