2
$\begingroup$

Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (Just as the smallest upper bound is $n^7$)

The reason I say that the function is in the Omega class of functions larger than $n^5$ is because of the limit definitions of complexity [Source]: $\require{enclose}$

$$\begin{array}{c|c|c} \text{Big-}\mathcal O\ \text{notation} & \text{Comparison notation} & \text{Limit definition}\\ \hline f \in \mathcal o(g) & f \; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px] \lt \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = 0\\ f \in \mathcal O(g) & f\; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\le \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} < \infty \\ f \in \Theta(g) & f\; {\scriptstyle \enclose{circle}{\bbox[7px]=}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} \in \mathbb{R}_{>0} \\ f \in \Omega(g) & f \;{\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\ge \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} > 0 \\ f \in \omega(g) & f\; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\ge \kern .07em}}\; g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = \infty \\ \end{array}$$

Using the limit definition of $\mathcal O$, we correctly identify that $n^5+n^7 \in \mathcal O(n^7)$ and $n^5+n^7 \notin \mathcal O(n^6)$

However, using the limit definition of $\Omega$ tells us that the function is in $\Omega(n^7)$! But isn't the largest lower bound for this function $n^5$?

$\endgroup$

2 Answers 2

3
$\begingroup$

The function $n^5 + n^7$ is big-$Ω$ of both. However, it is little-$\omega$ of $n^5$.

It happens that $n^5 + n^7 \in \Theta(n^7)$. These asymptotic-notations only describe the behavior of the function $f(n) = n^5 + n^7$ for large $n$, aka "for all $n > \textrm{some value}$". The function is a polynomial function, and the highest-degree term determines the order of growth.

From the definition of $Θ(g)$, it means that function $f$ is both big-$O$ and big-$Ω$ of $g$. The function is bounded by some constant multiple of $n^7$ for large $n$. Namely, the function is bounded above by $2n^7$ and below by $n^7$.

Nevertheless, $n^5 + n^7 \in \Omega{(n^5)}$; the function is of [strictly] greater order than a quintic. Equivalently, $n^5 \in O(n^5 + n^7)$.

$\endgroup$
0
0
$\begingroup$

Observe that $n^5+n^7 > n^7 \ge n^5, ~~\forall n \ge 1$. Then clearly, the 'largest lower bound' is $n^7$. Therefore, $n^5+n^7 = \Omega(n^7)$ as well as $n^5+n^7 = \Omega(n^5)$ and also $n^5+n^7 = \Omega(1)$, but we generally choose the one that is largest and more tight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.