3
$\begingroup$

I faced some problem that involves arithmetic over asymptotic functions. These are as follows:

  1. Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is:

    (a) $Ω(n)$
    (b) $O(n)$
    (c) $\Theta(n)$ (d) None of these

Solution to this was discussed as follows:

Let

  • $n = 5$
  • $f = 6$ so that $f = Ω(n)$ and
  • $g = -6$ so that $g = O(n)$ and
  • $h = 5$ so that $h = Ѳ(n)$
  • $f.g + h = -36 + 5 = -31 < n → f.g + h = O(n)$

Now let,

  • $g = 4$ so that $g = O(n)$ and
  • $f.g + h = 24 + 5 = 29 > n → f.g + h = Ω(n)$

Hence option 4 is correct, None of these.

Then I came across another problem

  1. Let $f(n)=Θ(n),g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)= ?$

    (a) $Ω(n)$ (b) $Ω(n^2)$ (c) $Θ(n)$ (d) $Θ(n^2)$

This problem was solved in completely different approach:

Using the definitions of notations:

$f(n)= θ(n)→ c_1.n<=f(n)<=c_2.n$ ... for $n>n_0$

$g(n)= θ(n)→ c_3.n<=g(n)<=c_4.n$ ... for $n>n_0$

$h(n)= Ω(n)→ h(n)>=c_5.n$ ... for $n>n_0$

Using the extended notations forms:

$c_1.c_3.n^2<=f(n)g(n)<=c_2.c_4.n^2$ ... for $n>n_0$

Taking $c_1,c_3=k_1$ and $c_2.c_4=k_3$

$k_1.n^2<=f(n)g(n)<=k_2.n^2$

Adding h(n)

$k_1.n^2+c_5.n<=h(n)+f(n).g(n)<=k_2.n^2$ ... for $n>n_0$

As $n^2>n$ for all $

$k_3.n^2<=h(n)+f(n).g(n)<=k_2.n^2$

Which simplifies to :

$f(n).g(n) + h(n) =Ω(n^2)$

Though I am able to appreciate both approaches, this leaves me a lot of confusion. I am not able to confidently apply these methods to each other, nor to other similar problems and reach the correct solution. Are these methods correct? In fact are these questions themselves correct? Is there more straightforward approach to solve such kind of problems?

$\endgroup$
  • $\begingroup$ The solution to problem 1 is totally wrong. You cannot substitute a value for $n$. A notation like $f(n) = \Omega(n)$ is asymptotic – it means absolutely nothing for any particular $n$. $\endgroup$ – Yuval Filmus May 6 '16 at 20:41
  • $\begingroup$ @YuvalFilmus I think you're misunderstanding the problem - it's saying that those functions are bounded by whatever is specified, therefore what they can actually be is a wide range of functions within their bounds. The author or professor showed a counter example with two legal functions that contradicted each other which proved option d $\endgroup$ – Nick Zuber May 6 '16 at 20:45
  • $\begingroup$ @NickZuber Perhaps the professor uses an unorthodox definition of asymptotic notation, which doesn't rely on asymptotics. In that case, I certainly wouldn't call it asymptotic functions. $\endgroup$ – Yuval Filmus May 6 '16 at 20:51
  • $\begingroup$ @YuvalFilmus I feel like we're on different pages here, what part defies the asymptotic nature of these functions? The idea behind these kinds of questions are to give a broad understanding of asymptotic bounds, for example when a questions says that $g(n)= O(n)$ it's saying that some function $g(n)$ has an upper bound of $n$, therefore can be any function within this bound. The idea of these questions is to find contradictions or prove that the propositions are true given the functions and their respective bounds. $\endgroup$ – Nick Zuber May 6 '16 at 20:55
  • $\begingroup$ @NickZuber The proposed answer to problem 1 does. Perhaps you missed it? $\endgroup$ – Yuval Filmus May 6 '16 at 20:56
2
$\begingroup$

One way to help understand what's going on conceptually would be to draw a linear graph of what each of these functions mean.

So for example, say we're given a problem that tells us:

$g_1(n)=\Theta(lg(n))$

$g_2(n)=O(n^2)$

$g_3(n)=\Omega(n)$

we can make a quick sketch of where they could be in relation to each other.

enter image description here

With this visual, we can get an idea of possible candidates for these functions.

So let's bring it back to one of the questions you had trouble understanding:

Let $f(n)=Θ(n), g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)=?$

We know that $f(n)$ and $g(n)$ are both tightly bounded at $n$, so if you multiply them together, you'll clearly get $\Theta(n^2)$.

Now if we also add some function $h(n)$ that we know has a lower bound of $n$, the result must be $\Theta(n^2)+\Omega(n)$ which we can reduce to $\Omega(n^2)$, since an additional $...+\Omega(n)$ factor will be at its lowest value $n$ but there is no bound on how high this function can be (it could be anywhere from $n$ to $n^{1000}$ since there's no telling what an upper bound is), so we can conclude that it's $\Theta(n^2)+n=\Omega(n^2)$

$\endgroup$
  • $\begingroup$ Applying your analogy to my first question ($f(n)= Ω(n), g(n)= O(n)$ and $h(n)= Ѳ(n), f(n). g(n) + h(n)=?$), can we form graph and conclude it like this? i.e. can we generalize that if there are two function going in two opposite directions, we cannot conclude anything about the asymptotic complexity of the function involving the multiplication of these two, unless we are given some more conditions (say in this case all functions are non negative)? $\endgroup$ – anir May 7 '16 at 8:18
  • $\begingroup$ @anir correct, or rather we're given more bounds on those functions. When you multiply a function that's O(n) but one that's $\Omega(n)$, the $\Omega(n)$ function could very well be $n$ or $n^2$ or even $n^{1000000}$ since we know nothing about its upper bound. Conversely the same is true about some $O(n)$ function - we don't know it's lower bound so it could be $n^{-5}$ for all we know. Does this help? $\endgroup$ – Nick Zuber May 7 '16 at 10:30
1
$\begingroup$

The first question is somewhat ambiguous, since the answer depends on whether you're assuming all functions are non-negative or not; we usually make this assumption in complexity theory. In that case, $f(n)g(n) + h(n) \geq h(n)$, and so $f(n) g(n) + h(n) = \Omega(n)$. On the other hand, it's not always the case that $f(n)g(n) + h(n) = O(n)$: for example, if $f(n) = g(n) = h(n) = n$ then $f(n)g(n) + h(n) = \Theta(n^2)$.

For the second question, again we get $f(n) g(n) + h(n) \geq f(n) g(n) = \Omega(n^2)$. On the other hand, if $f(n) = g(n) = n$ and $h(n) = n^3$ then $f(n) g(n) + h(n) = \Theta(n^3)$, showing that it's not necessarily the case that $f(n) g(n) + h(n) = O(n^2)$.

I skipped some steps; the details are as in the answer to the second question, though that answer is only partial (it doesn't show that you can't conclude that $f(n) g(n) + h(n) = O(n^2)$).

On the other hand, the answer to first question is completely wrong: asymptotic notation doesn't say much about any specific $n$ (other than the usual assumption that all functions are non-negative). In particular, if $f(5) > 5$ then we can't conclude that $f(n) = \Omega(n)$; perhaps $f(n) = 5$ for all $n$, for example.

You would do well ignoring whoever answered the first question. Unfortunately they have no idea what they're talking about.

$\endgroup$
  • $\begingroup$ About 2nd question, what if $f(n)=g(n)=n^3$ and $h(n)=n^4$? Will it be $f(n)g(n)+h(n)=\Theta(n^4)$? If yes, does that mean we cannot conclude anything firm in question 2?... $\endgroup$ – anir May 7 '16 at 7:25
  • $\begingroup$ ...Some more about 2nd question, if we conclude that $i(n)=f(n)g(n)+h(n)=Θ(n^3)$, does that mean it cannot be $Ω(n^2)$? Somehow I just felt that it can be both at the same time. $Ω(n^2)$ implies that the function is asymptotically greater than $n^2$. So it can assume any value greater than $n^2$, at the same time it may be asymptotically equal to certain function greater than $n^2$, in your case $n^3$. So I feel in case of $i$, it is both asymptotically $>n^2$ and $=n^3$ i.e. $Ω(n^2)$ and $Θ(n^3)$... $\endgroup$ – anir May 7 '16 at 7:25
  • $\begingroup$ ...So I felt that for $i$, the bound $Ω(n^2)$ will always hold regardless what is the bound in terms of $Θ(\text{some higher order function})$ (be it $Θ(n^3)$ or $Θ(n^4)$). Am I wrong? $\endgroup$ – anir May 7 '16 at 7:26
  • $\begingroup$ Thanks, I had a small mistake there. In your example, $i(n)=\Theta(n^6)$. In question 2 you indeed get $i(n)=\Omega(n^2)$, but you cannot conclude more than that, as my (fixed) counterexample shows. $\endgroup$ – Yuval Filmus May 7 '16 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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