CSCE 411 Lecture 5

Lecture Slides

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

Example Limit Superior

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} f(n) &= n^2 + (-1)^n \, n^2 + n \\ g(n) &= n^2 \\ \limsup_{n\to\infty} \frac{|f(n)|}{|g(n)|} &= 2 \end{align}}

Therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n)} be the worst-case time on a sequence of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} keys.

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

If $n>1$, then $T(n)=2\,T\left({\frac {n}{2}}\right)+\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)=\Theta (n)$. Therefore, $T(n)=\Theta \left(g(n)\log {n}\right)=\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) << g(n)} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta(g(n))}
2. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \approx g(n)} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta(g(n)\log{n})}
3. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) >> g(n)} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(n) = \Theta(f(n))}

Other D&C Algorithms

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