CSCE 411 Lecture 5

Lecture Slides

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

Example Limit Superior

${\begin{aligned}f(n)&=n^{2}+(-1)^{n}\,n^{2}+n\\g(n)&=n^{2}\\\limsup _{n\to \infty }{\frac {|f(n)|}{|g(n)|}}&=2\end{aligned}}$

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)=\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 $f(n)<<g(n)$ then $T(n)=\Theta (g(n))$
2. If $f(n)\approx g(n)$ then $T(n)=\Theta (g(n)\log {n})$
3. If $f(n)>>g(n)$ then $T(n)=\Theta (f(n))$

Other D&C Algorithms

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