Introducing Analysis of Algorithms

Videos (0 mins)

No videos for today’s class.

Reading (~ 50 mins)

This is a more challenging reading than usual. Please take your time. You’ll need it for the warmup problems!

Discrete Mathematics and Its Applications by Kenneth Rosen, Section 8.3, up to and including Example 9, pages 527-532.

  • It is ok to skip Examples 3 and 4.

Warmup

Problem 1

Suppose that \(f(n) = 2f(n/2) + 3\) whenever \(n\) is an even positive integer, and that \(f(1) = 5\).

Find \(f(2)\), \(f(8)\), \(f(64)\), and \(f(1,024)\). Please do at least \(f(2)\) and \(f(8)\) by hand. You can either code a function to compute \(f(64)\) and \(f(1,024)\) or do those by hand as well.

Problem 2

Consider the following algorithm called trisection search. Trisection search is an algorithm that, given a sorted list \(L\) of integers, determines whether or not a given integer \(x\) is an element of \(L\). For convenience, let’s assume that the length of \(L\) is \(3^p\) for some integer \(p\).

For example, our algorithm should return \(\mathrm{True}\) for \(x = 5\) and \(L = [0, 2, 3, 5, 7, 8]\) but \(\mathrm{False}\) if instead \(x = 4\). You may know of bisection or binary search, which solves the same problem.

Here’s the algorithm:

Algorithm \(\mathrm{TrisectionSearch}(x, L)\):

  1. If \(L\) has length 1, then return \(\mathrm{True}\) if the single element of \(L\) is equal to \(x\), and return \(\mathrm{False}\) otherwise.
  2. Divide \(L\) into 3 equal pieces, called \(L_1\), \(L_2\), and \(L_3\). Let the final elements of each of these lists be \(\ell_1\), \(\ell_2\), and \(\ell_3\) respectively.
    • If \(x \leq \ell_1\), return \(\mathrm{TrisectionSearch}(x, L_1)\).
    • Else, if \(\ell_1 < x \leq \ell_2\), then return \(\mathrm{TrisectionSearch}(x, L_2)\).
    • Else, if \(\ell_2 < x\), then return \(\mathrm{TrisectionSearch}(x, L_3)\).

Part A

Give a big-\(O\) estimate for the number of comparisons between integers used by trisection search on a list of length \(n = 3^p\). To do so, use the following steps:

  1. Write down and justify a recurrence relation describing the number of comparisons required (Example 1 from the reading will be helpful).
  2. Apply a theorem from the reading to obtain a big-\(O\) estimate.

Part B

For each

Respond with a “true” or a “false” and a quick explanation to each of the following two statements:

  1. Trisection search requires exactly as many comparisons between integers as binary search.
  2. Trisection search requires no more than 10% more comparisons than binary search.
  3. If \(n\) increased by a factor of 10, then the number of comparisons required by binary and trisection search would both increase by a similar (but not exactly the same) factor.

(Optional): Part C

Define a modified version of the algorithm above that splits a sorted list into \(k\) equal-sized pieces in each recursive step. Give a big-\(O\) estimate for the runtime on a list of length \(n = k^p\).



© Phil Chodrow, 2023