CSCE 411 Lecture 5

Lecture Slides

« previous | Wednesday, September 5, 2012 | next »

Example Limit Superior

$\begin{array}{rl}f(n)& =n^2+(-1{)}^n{n}^2+n\\ g(n)& =n^2\\ \underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|f(n)|}{|g(n)|}& =2\end{array}$

Therefore $f(n)\in O(g(n))$

Divide and Conquer

1. Divide a problem into subproblems
2. Recursively solve subproblems
3. Combine solutions to subproblems to get solution to original problem

Example: Merge-sort

1. Divide the input in half
2. Recursively sort the two halves (basis is a sequence with 1 key)
3. Combine two sorted subsequences by merging them

Recurrence Relation

How long does Merge-sort take?

Let $T(n)$ be the worst-case time on a sequence of $n$ keys.

If $n=1$, then $T(n)=\mathrm{\Theta }(1)$ (constant)

If $n>1$, then $T(n)=2T\left(\frac{n}{2}\right)+\mathrm{\Theta }(n)$ (2 × time of solving each half and then the merge)

Two ways to solve:

1. Expand several times, guess pattern, and try to prove by induction. (hard!)
2. Master theorem

Using the master theorem, $g(n)=n^{{\log }_{2}2}=n$ and $f(n)=\mathrm{\Theta }(n)$. Therefore, $T(n)=\mathrm{\Theta }(g(n)\log n)=\mathrm{\Theta }(n\log n)$

Master Theorem

(See Master Theorem→)

Given a recursive function (recurrence relation) of the form

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$

Let $g(n)=n^{{\log }_{b}a}=a^{{\log }_{b}a}$. This represents the number of "leaf operations" in the divide-and-conquer tree

1. If $f(n)<<g(n)$ then $T(n)=\mathrm{\Theta }(g(n))$
2. If $f(n)\approx g(n)$ then $T(n)=\mathrm{\Theta }(g(n)\log n)$
3. If $f(n)>>g(n)$ then $T(n)=\mathrm{\Theta }(f(n))$

Other D&C Algorithms

• Mathematics
  • Converting Binary to Decimal
  • Integer Multiplication
  • Matrix Multiplication
  • Matrix Inversion
  • Fast Fourier Transform