Homework 2, Algorithm Performance.

Short Description:

Answer questions relating to algorithm performance analysis.

Formal Description

Please do the following:
  1. 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.
    1. Which implementation executes fewer instructions for n=10?
    2. Which implementation executes fewer instructions for n=1,000?
    3. What does this example illustrate about constants and the size of the input?
  2. 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.
    1. Searching an array containing 500 integers.
    2. Evaluating a polynomial of degree 30.
    3. Finding the shortest path between two cities in a road network containing 10,000 roads and 2,000 cities.
  3. The constants don't matter.
    Consider: f(n)=1000n and g(n)=n2
    1. Which function is larger when n=10?
    2. Which function is larger when n=10,000?
    3. Are the two functions in the same Big-O class? Explain.
    4. What does this tell us about why asymptotic analysis ignores constant coefficients?
  4. 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
  5. Which algorithm would you choose?
    Algorithm Running Time
    A 50n
    B 2n2+100
    C 3log2n+500
    1. Which algorithm has the best asymptotic performance?
    2. Which algorithm would you expect to perform best for very large n?
    3. Is it possible for Algorithm A or B to be faster than Algorithm C for some small values of n? Explain.
    4. 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.

Required Files

Please submit an electronic document with you answers.

Submission

Submit the assignment to the D2L folder Homework2 by the due date.