-1
$\begingroup$

I am struggling still with this equations...from my class materials....

This time we deal with lower bound -> BIG OMEGA:

I know that:

$\Omega(g(n)) = \{f(n) : \exists c, n_0 > 0\,\forall n\ge n_0\ \ cg(n) \le f(n)\}$

1) $\frac 13 n^2 − 3n = \Omega(n^2)$

$\frac 13n^2 − 3n \ge cn^2$, if $c \le \frac 13 − \frac 3n$ which is true if $c = \frac 16$ and $n > 18$. is that right???

2) $(n + a)^b = \Omega(n^b)$ for $a, b > 0$

Here i am not sure.

$(n + a)^b \ge cn^b$, if $c <= \frac{(n+a)^b}{n^b}$ for some $a,b > 0$

HOW this works?

2 Answers 2

1

Write $\frac{(n+a)^b}{n^b}$ as $\left(\frac{n+a}n\right)^b = \left(1 + \frac{a}{n}\right)^b$. This goes toward $1$ as $n\to\infty$, so you can use any $c<1$ if you choose a large enough $n_0$ to go with it.

0

$\begin{equation} \begin{split} (n+a)^b & = \sum_{k=0}^b {{b}\choose{k}}n^{b-k}y^{k} \\ & = n^b+\sum_{k=1}^b {{b}\choose{k}}n^{b-k}y^{k} \\ & \ge n^b \end{split}\end{equation}$