2-3-2025

$\Omega$ and $\Theta$

• Reminder:
  • Defn. $f(n)=O(g(n))$ means:
  • $\exists n_0\ge 0$, $\exists c>0$ s.t. if $n\ge n_0$ then $f(n)\le cg(n)$ Frequently well use $x$ instead of $n$
• Doesn’t really matter except:
• Typically $n$=size of list or # nodes or …
• so it’s a whole number like 8 or 0 or 7 or… $n\in \mathbb{N}$
• whereas $x$ could be any real number. Thnk of $O$ as an upper bound!

a) Defn. We say $f(n)=\Omega (g(n))$ if

$$\exists n_0\ge 0,\exists B>0\text{ s.t. }n\ge n_0\to f(n)\ge Bg(n)$$

b) Def. We say $f(n)=\Theta (g(n))$ if

$$\exists n_0{\ge }_0,\exists B>0,\exists C>0\text{ s. t. }n{\ge }_0\to Bg(n)\le f(n)\le Cg(n)$$

Example of proving $\Omega$:

(a) Prove: $3n^2+1=\Omega (n^2)$ Want: $3n^2+1=B{n}^2\dots$ When doing $\Omega$, you can chuck out the pluses. HAHA! $3n^2+1\ge 3n^2$ always! Pf: Observe that $\forall n\in \mathbb{Z}$, $3n^2+1\ge 3n^2$ always, so defn sat. w/ $B=3$ and $n_0=0$. (b) Prove: $3n^2-n=\Omega (n^2)$ Want: $3n^2-n\ge B{n}^2\dots$ $3n^2-n\ngeqq 3n^2$ Well look, $n\le n^2$ when $n\ge 1$. In which case $3n^2-n\ge 3n^2-n^2=2n^2$. AHA! :) Pf: Observe that if $n\ge 1$ then $n^2\ge n$ so

$$3n^2-n\ge 3n^2-n^2=2n^2$$

So the definition is satisfied with witness $B=2$ and $n_0=1.$

(c) Prove: $n^2-n+1=\Omega (n^2)$

Well: $n^2-n+1\ge n^2-n$ Again $n\le n^2$ if $n\ge 1$ so $n^2-n\ge n^2-n^2=0$ aw shucks! Issue is: we eliminated it all - could we subtract less? Well: $n\le \frac{1}{2}{n}^2$ when $2n\le n^2$ which is when $n\ge 2$. Now $n^2-n\ge n^2-\frac{1}{2}{n}^2=\frac{1}{2}{n}^2$ and we’ve got some $n^2$ left.

Pf: Observe that if $n\ge 2$, then $n\le \frac{1}{2}{n}^2$ and then $n^2-n+1\ge n^2-n\ge n^2-\frac{1}{2}{n}^2=\frac{1}{2}{n}^2$ So defn is sat when $n_0\ge 2$ and $B=\frac{1}{2}$.

(d) Prove: $n\log n+n-100\log n=\Omega (n\log n)$

We can throw out the $+n$ since we’re proving an $\Omega$.

$$n\log n+n-100\log n\ge n\log n-100\log n$$

Need $100\log n\le$ some multiple of $n\log n$ but not an entire than $n\log n$.

$100\log n\le \frac{1}{5}n\log n$ when $100\le \frac{1}{5}n$. $n\ge 500$ Pf: If $n\ge 500$ then $\frac{1}{5}n\ge 100$ so $100\log n\le \frac{1}{5}n\log n$ and so

$$n\log n+n-100\log n\ge n\log n-100\log n\ge n\log n-\frac{1}{5}n\log n=\frac{4}{5}n\log n$$

So defn sat when $n_0=500$ and $B=\frac{4}{5}$

(4) When possible give $\Theta$ instead of $O,\Omega$. Why? Well: $x^2+x=O(x^2)$ but $x^2+x=O(x^3)$ too, and $x^2+x=O(x^{100})$ too… Whereas $x^2+x=\Theta (x^2)$ but $x^2+x\ne \Theta (x^3)$. If you can give both an upper and lower bound, that’s better.

(5) Intuition: Whenever dealing with an expression, it’s always $\Theta$ of the “largest” term. ex. $x^2+x+3=\Theta (x^2)$ ex. $x\log n+x^3-x+1=\Theta (x^3)$

Largest goes in order

$$1,\log n,n,n\log n,n^2,n^2\log n,\dots ,2^n,3^n,\dots ,n!,n^n,\dots$$ $$h\ell othererefjaejf\mathbb{k}$$