CSC 454/654 - Spring 2021 - Assignment 1 - Due Feb 4, 2021

This is a “warm-up” assignment that is shorter than future assignments will be. You only have one week (rather than the normal 2 weeks) for this assignment, and it will count for half the amount of the other assignments (it will be graded out of 50 points).

  1. The following algorithm tests to see if there are duplicates in an input array with \(n\) elements: \(A=\langle a_1,a_2,\ldots,a_n\rangle\).

             DupSearch(A)
       1.  for i = 1 to n-1
       2.      for j = i+1 to n
       3.          if A[i] == A[j]
       4.              return true
       5.  return false

    Do a careful runtime analysis of this algorithm, using explicit constants like we did for the examples in class, with results for both the best case and worst case running times.

  2. Consider algorithms with the following time complexities:

    Algorithm 1: \(5n\lg n\)

    Algorithm 2: \(n!\)

    Algorithm 3: \(3^n\)

    Algorithm 4: \(50n\)

    Algorithm 5: \(n^2\)

    Algorithm 6: \(2n^3\)

    1. Assuming that the above formulas give the running times of these algorithms in microseconds, make a table showing the running time of each algorithm for input sizes of \(n=10\), \(n=100\), and \(n=1000\). If a running time turns out to be more than \(10^{50}\) seconds, you can simply write ``too large’’ in the table.

    2. Write the algorithms in order of slowest to fastest when \(n=10\).

    3. Write the algorithms in order of asymptotic running time (slowest to fastest).

    4. For what values of \(n\) is Algorithm 4 faster than Algorithm 1?

  3. Prove or disprove each of the following conjectures using just the definitions of asymptotic notation and basic algebra:

    1. Let \(f(n)\), \(g(n)\), and \(h(n)\) be positive functions. Prove that if \(f(n)\) is \(O(g(n))\) and \(g(n)\) is \(O(h(n))\), then \(f(n)\) is \(O(h(n))\). (In other words, big-Oh notation is transitive)

    2. Prove that \((cn)^n\) is \(O(n^{2n})\) for any constant \(c>0\). (Note: Be careful with names of constants when you write up this proof! You’ll be applying the big-Oh definition, which includes a constant named \(c\), but that’s not the same as the \(c\) in this problem statement. Create new names for constants when necessary!)

    3. Prove that \((3n)^n\) is not \(O(n^{n+1})\)