Homework 2, Algorithm Performance.
Short Description:
Answer questions relating to algorithm performance analysis.
Formal Description
Please do the following:- Hardware and algorithms
Suppose two programmers implement the same algorithm.
- Programmer A's program executes 10n2 + 20n + 100 instructions.
- Programmer B's program executes 50n2 + 5n + 10 instructions.
- Which implementation executes fewer instructions for n=10?
- Which implementation executes fewer instructions for n=1,000?
- What does this example illustrate about constants and the size of the input?
- Defining n for a problem.
For each of the following problems, identify a reasonable definition of the input size \(n\). For each answer, briefly explain why your choice is reasonable.- Searching an array containing 500 integers.
- Evaluating a polynomial of degree 30.
- Finding the shortest path between two cities in a road network containing 10,000 roads and 2,000 cities.
- The constants don't matter.
Consider: f(n)=1000n and g(n)=n2- Which function is larger when n=10?
- Which function is larger when n=10,000?
- Are the two functions in the same Big-O class? Explain.
- What does this tell us about why asymptotic analysis ignores constant coefficients?
- Rank the following functions from slowest-growing to fastest-growing as n becomes very large.
n2, n!, log2n, 2n, n, nlog2n
Then explain why n! eventually grows faster than 2n - Which algorithm would you choose?
Algorithm Running Time A 50n B 2n2+100 C 3log2n+500 - Which algorithm has the best asymptotic performance?
- Which algorithm would you expect to perform best for very large n?
- Is it possible for Algorithm A or B to be faster than Algorithm C for some small values of n? Explain.
- Why doesn't Big-O tell us exactly which program will run faster on a particular computer for a particular input?
Note
This homework was designed with the assistance of chatGPT. I submitted the notes pages and it provided some suggestions for questions. You are lucky that I am not as thorough as chatGPT, it had 20 multipart questions.As I have done, if you work in a group or use AI, you are required to state this. In addition, you are required to state the percentage of the work you had AI do for you.