More Asymptotics

Videos

No new videos today. Reviewing the videos from last class might be helpful!

Reading

Connecting Discrete Mathematics and Computer Science by David Liben Nowell: Section 6.5 (pages 60-67)

Warmup

Problem 1

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

Part A

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.

Part B

Determine the asymptotic behavior of \(f(n)\) using Big-Oh notation, using a theorem from the readings. That is, find a function \(g(n)\) such that \(f(n) \in \Theta(g(n))\) (recall that this means both \(f(n) \in O(g(n))\) and \(f(n) \in \Omega(g(n))\)).

Problem 2

MergeSort works by dividing a given array into two halves, recursively sorting each half, and then merging the two sorted halves back together.

But wait! What if we recursively split the array into \(\ell\) pieces, where \(\ell \geq 3\)? Let’s call this algorithm \(\ell\)-MergeSort; so 2-MergeSort is just the usual MergeSort algorithm.

Part A

Let \(T(n)\) be the number of comparisons performed by \(\ell\)-MergeSort on an array of length \(n\), where \(n\) is a power of \(\ell\). Determine a recurrence relation describing \(T(n)\). You can assume that merging \(\ell\) sorted arrays of length \(n/\ell\) each requires at most \(cn\) comparisons for some constant \(c > 0\).

Your recurrence should look similar to Ex. 6.30 in Rosen.

Part B

Determine the asymptotic estimate for the number of comparisons performed by \(\ell\)-MergeSort on an array of length \(n\). Does your estimate depend on \(\ell\)? Are any \(\ell\)-MergeSort algorithms asymptotically faster than others?