In algorithm development, the time and space required for algorithm completion is paramount. As users, we know that when a computer process takes too long, we try to avoid it. This truth encourages all IT and computer-based companies to produce faster products and services.
For this assignment, write a one- to two-page paper that includes all required algorithms and pseudocode describing the time and space complexity of algorithms. Include the following:
Answer the following questions:
What is time complexity?
What is space complexity?
Compare and contrast polynomial time algorithms and nondeterministic polynomial (NP) time algorithms (one paragraph minimum).
Provide an example of an algorithm for each worst-case run times:
O( n).
O( nk). Note that this is called polynomial-time, where k is any number greater than 1.
NP-time.
Hint: Quick sort is an algorithm that runs in O( nlog n) time.