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$

1 Answer 1

2
$\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

Your Answer

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

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