The second concern is about finding the answer to the following question:

At first glance, this question looks quite simple to answer. However, for a certain class of algorithms, researchers have unsuccessfully spent decades verifying whether a particular solution generated by an algorithm is also the best and that no other solution exists that can give better results. So, it becomes important that we first understand the problem, its requirements, and the resources available to run the algorithm. We need to acknowledge the following statement:

So, understanding the problem and its complexities is important and helps us estimate the resource requirements.

Before we start looking deeper into this, first, let's define a couple of terms here:

• Polynomial algorithm: If an algorithm has a time complexity of O(n^k ), we call it a polynomial algorithm, where k is a constant.
• Certificate: A proposed candidate solution produced at the end of an iteration is called a certificate. As we progress iteratively in solving a particular problem, we typically generate a series of certificates. If the solution is moving toward convergence, each generated certificate will be better than the previous one. At some point, when our certificate meets the requirements, we will choose that certificate as the final solution.

In Chapter 1, Overview of Algorithms, we introduced Big O notation, which can be used to analyze the time complexity of an algorithm. In the context of analyzing time complexity, we are looking at the following different time intervals:

• The time it takes for an algorithm to produce a proposed solution, called a certificate (t_r)
• The time it takes to verify the proposed solution (certificate), t_s