Question

1. Suppose a problem can be solved by an algorithm in O(n²) as well as another algorithm in O(2ⁿ). Will one algorithm always outperform the other?

2. Give an example of a polynomial problem. Give an example of a nonpolynomial problem. Give an example of an NP problem that as yet has not been shown to be a polynomial problem.

3. If the time complexity of algorithm X is greater than that of algorithm Y, is algorithm X necessarily harder to understand than algorithm Y? Explain your answer.

Answer 1

These O(n²) and O(2n) are asymptotic time complexitites i.e for larger values of inputs how an algorithm performs.n being the no. of inputs here O(2n) will always perform better and an the efficiency of algorithm depends upon how it is performing on larger inputs rather than smaller inputs.So ,yes O(2n) is much better than O(n²).

An algorithm is polynomial if for some k>0, its running time on inputs of size n is O(n^k) i.e maybe linear,quadratic and more.

Example-All Pair Shortest Path Problem(Floyd Warshall Algorithm) is a Polynomial time problem .

An algorithm is non polynomial if it takes some exponential time to run for inputs i.e maybe 2^n.

^{Example-Travelling Salesman Problem}

^{Sudoku is a game which is an example of NP problem which is not yet shown to be a polynomial problem}

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution.Every code takes time to execute.Time taken by the the lines of code written to execute is known as time complexity of the code.Lesser the time complexity of code,more efficiently the code runs i.e takes less time to run.So it's not like if the time complexity is less then the algorithm is easier to understand.It just effects execution time.There is no co-relation between time complexity of a problem and its understandibility.