2-5-2025

Handy Limit Theorems

Theorem. Suppose $f(x)$, $g(x)$ are functions. Then:

$$\underset{x\to \infty }{\lim }\frac{f(x)}{g(x)}\ne \infty \to f(x)=\mathcal{O}(g(x))$$ $$\underset{x\to \infty }{\lim }\frac{f(x)}{g(x)}\ne 0\to f(x)=\Omega (g(x))$$ $$\underset{x\to \infty }{\lim }\frac{f(x)}{g(x)}\ne 0,\infty \to f(x)=\Theta (g(x))$$

Proof. omitted

Ex. To show $n^2+n-10=\Theta (n^2)$,

$$\underset{n\to \infty }{\lim }\frac{n^2+n-10}{n^2}=\underset{n\to \infty }{\lim }\frac{2n+1}{2n}=\underset{n\to \infty }{\lim }\frac{2}{2}=1$$

Since $1\ne 0$ and $1\ne \infty$, $n^2+n-10$ is $\Theta (n^2)$. $QED$

Ex. To show $n^2=\mathcal{O}(2^n)$,

$$\underset{n\to \infty }{\lim }\frac{n^2}{2^n}=\underset{n\to \infty }{\lim }\frac{2n}{2^n\ln n}=\underset{n\to \infty }{\lim }\frac{2}{2^n(\ln n{)}^2}=0$$

Because $0\ne \infty$, but $0=0$, $n^2=\mathcal{O}(2^n)$.

Analysis of Pseudocode

There are a few things we’ll generally do when analyzing pseudocode:

• Find $T(n)$=$\Theta (?)$ or $\mathcal{O}$ if not possible
• Count the number of times something occurs
• Finding the space required for any given $n$, so $S(n)=\Theta (?)$ or $\mathcal{O}$…

Ex.

for i=1 to n^2 inclusive:
	for j=i to i inclusive:
		print "Hi!"
	end for
	if i is even:
		print "Hi!"
	end if
end for

Q: How any times is Hi! printed? ${\sum }_{i=1}^{n^2}{\sum }_{j=1}^{i}1+\lfloor \frac{n^2}{2}\rfloor$ times Second for prints ${\sum }_{j=1}^{i}1$ times Without conditional prints

\sum_{i=1}^{n^2} \sum_{j=1}^i 1 $$ times.

\left\lfloor \frac{n^2}{2} \right\rfloor

is the number of times $i$ is even between $[1,n^2] \in \mathbb{Z}$. So overall, `Hi!` is printed $$\left(\sum_{i=1}^{n^2} \sum_{j=1}^i 1\right)+\left\lfloor \frac{n^2}{2} \right\rfloor=\left(\sum_{i=1}^{n^2} i \right)+\left\lfloor \frac{n^2}{2} \right\rfloor=\frac{n^2(n^2+1)}{2}+\left\lfloor \frac{n^2}{2} \right\rfloor$$ times. For time, technically, everything takes time! ```Ruby sum = 0 # <- c1 time (c1 is constant) for j=i to n inclusive: # <- c2 per iteration sum = sum + i # <- c3 time end for # <- c4 per iteration ``` So, $T(n)=c_{1}+\sum_{i=1}^{n}(c_{2}+c_{3}+c_{4})$. However, if all we want is $\Theta$ or $\mathcal{O}$ or $\Omega$, then * "Maintenance" (loop overhead) for `for` loops do not need to be counted ($c_{2},c_{4}$) as long as something happens inside ($c_{3}$) * Constant code before or after other code which takes time ($c_{1}$) can be ignored. So, good enough for $\Theta$ to say $T(n)=c_{3}n=\Theta(n)$.