CSCE 411 Lecture 4

Lecture Slides

« previous | Monday, September 3, 2012 | next »

Limit Superior

A tool used in Asymptotic Analysis.

The limit of a sequence might not exist:

$f(n)=1+(-1{)}^n⟶li{m}_{n\to \mathrm{\infty }}f(n)=DNE$

Supremum

The supremum $b$ of a set of real numbers $S$ is the smallest real number $b$ such that $b\ge s$ for all $s$ in $S$

Notation: $b=\mathrm{s}\mathrm{u}\mathrm{p}S$

• $\mathrm{s}\mathrm{u}\mathrm{p}\{1,2,3\}=3$
• $\mathrm{s}\mathrm{u}\mathrm{p}\{x\mid x^2<2\}=\sqrt{2}$
• $\mathrm{s}\mathrm{u}\mathrm{p}\{(-1{)}^n-\frac{1}{n}|n\ge 0\}=1$

Limit Superior

The Limit superior of a sequence $x_n$ of real numbers is defined as

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{x}_n=\underset{n\to \mathrm{\infty }}{\lim }\left(\mathrm{s}\mathrm{u}\mathrm{p}\{x_m\mid m\ge n\}\right)$

Note: the limit superior always exists in the extended real line (including ±∞)

Asymptotic Applications

(complicated function of $n$) = (simple function of $n$) + (bound for size of error in terms of n)

For example, $1^2+2^2+3^2+\dots +n^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}=\frac{n^3}{3}+O(n^2)$

Bold Conjecture

$1^k+2^k+3^k+\dots +n^k=\frac{n^{k+1}}{k+1}+O(n^k)$

Proof. Estimate the sum $S(n)=1^k+2^k+3^k+\dots +n^k$ as an integral:

$\begin{array}{rl}S(n)& <\underset{1}{\overset{n+1}{\int }}{x}^k\mathrm{d}x=\frac{(n+1{)}^{k+1}}{k+1}\\ S(n)& >\underset{0}{\overset{n}{\int }}{x}^k\mathrm{d}x=\frac{n^{k+1}}{k}\end{array}$