2
$\begingroup$

I know the definitions of this notations

  1. Big $\mathcal{O} \; : \enspace T(n) \in \mathcal{O}(f(n))$ if and only if $∃ \, c, n_0$, such that $T(n) \leq c \cdot f(n) \enspace \forall \,n \geq n_0$.
  2. Big $\Omega \; : \enspace T(n) \in \Omega(f(n))$ if and only if $∃ \, c, n_0$, such that $T(n) \geq c \cdot f(n) \enspace \forall \,n \geq n_0$.
  3. Big $\Theta \; : \enspace T(n) \in \Theta(f(n))$ if and only if $∃ \, c_1, c_2, n_0$ such that $c_1 f(n) \leq T(n) \leq c_2 f(n) \enspace$ $\forall \,n \geq n_0$.

I'm having trouble manipulating this definitions to prove some notation for example:

  • Suppose that $f = \Theta(g)$ and $g = \Theta(h)$. Prove that $f = \Theta(h)$
  • Suppose that $f$ and $g$ are two non-negative functions such that $g = \mathcal{O}(f)$. Prove that $f + g = \Theta(f)$.

Is there anything that could help me? I've read, watch videos but nothing helps me clarifying to prove these notations. Anything helps thanks. Also if you're a tutor and there's a way to set up a meeting it would help.

$\endgroup$
7
  • 1
    $\begingroup$ Please format your question to be more readable, also use Mathjax. That way people won't be deterred to read it :) $\endgroup$ Mar 18, 2021 at 19:00
  • 1
    $\begingroup$ Oh no. You can just edit it with the Edit button under your question. This is MathJax $\endgroup$ Mar 18, 2021 at 19:07
  • 1
    $\begingroup$ I have edited your question, now its your turn to make it pretty. This question is a good example. Try to break the question into lines to improve its readability. Basically the more effort you put in the more likely people will answer you. Make it look as good as you would want want something you read to look. $\endgroup$ Mar 18, 2021 at 19:10
  • 1
    $\begingroup$ Thanks, i'm doing it right now will take a couple of minutes. How do i break it in lines? I kept clicking enter but never happened. @LordCommander $\endgroup$
    – leomarrg1
    Mar 18, 2021 at 19:11
  • 1
    $\begingroup$ @LordCommander Is this better? In, stackoverflow i always get in trouble with doing a question. $\endgroup$
    – leomarrg1
    Mar 18, 2021 at 19:27

2 Answers 2

0
$\begingroup$

Considering the first problem:

1.) Because $f \in \Theta(g)$ there must exist $c_1, c_2$ and $n_0$ such that

$$ c_1 g(n) \leq f(n) \leq c_2 g(n) \tag{1}$$

for all $n \geq n_0$.


2.) Because $g \in \Theta(h)$ there must exist $\tilde{c}_1, \tilde{c}_2$ and $\tilde{n}_0$ such that

$$ \tilde{c}_1 h(n) \leq g(n) \leq \tilde{c}_2 h(n) \tag{2}$$

for all $n \geq \tilde{n}_0$.


3.) Combining 1.) and 2.) yields

$$c_1 \tilde{c}_1 h(n) \leq f(n) \leq c_2 \tilde{c_2} h(n) \tag{3}$$

Therefore there exist $\hat{c}_1, \hat{c}_2$, namely $\hat{c}_1 = c_1 \tilde{c}_1$ and $\hat{c}_2 = c_2 \tilde{c}_2$ and a $\hat{n}_0 = \max \{ n_0, \tilde{n_0} \}$ such that $f$ satisfies the conditions for being an element of $\Theta(h)$, i.e. $f \in \Theta(h)$


P.S.: Why $\hat{n}_0 = \max \{ n_0, \tilde{n_0} \}$? Because you want both inequalites to hold, in order to insert them into each other. The first one holds for all $n \geq n_0$, the second one holds for all $n \geq \tilde{n}_0$ and therefore a combination of those two can only hold for all $n \geq \hat{n}_0 = \max \{ n_0, \tilde{n}_0 \}$


Edit 1 I numbered the inequalities for better reference.

Row $(1)$ consists of two inequalities, namely $c_1 g(n) \leq f(n)$ and $f(n) \leq c_2 g(n)$. These inequalities are true for all $n \geq n_0$.

Row $(2)$ consists again of two inequalities, namely $\tilde{c}_1 h(n) \leq g(n)$ and $g(n) \leq \tilde{c}_2 h(n)$. These inequalities are true for all $n \geq \tilde{n}_0$.

Note, that $n_0$ and $\tilde{n}_0$ do not necessarily have to be the same.

We insert the inequalities of $(1)$ and $(2)$ into each other to obtain $(3)$. This only makes sense if the inequalities we are inserting are indeed true. But if $n_0 < \tilde{n}_0$, then row $(1)$ is still true for all $n \geq \tilde{n}_0$. Otherwise, if $n_0 > \tilde{n}_0$ then row $(2)$ is still true for all $n \geq n_0$. So you choose the greater of these two, i.e. $\max \{ n_0, \tilde{n}_0 \}$ in order for both rows $(1)$ and $(2)$ to hold. Then you have no problems combining them.

$\endgroup$
8
  • $\begingroup$ I'm having trouble understanding from where the max came from and when to use it. How did you got to combine them? Is combining them part of proving any asymptotic notations? $\endgroup$
    – leomarrg1
    Mar 18, 2021 at 20:09
  • $\begingroup$ I updated my answer, I hope it is more clear now. The point is, that by definition you need to find a $\hat{n}_0$ such that row $(3)$ holds. $\endgroup$
    – Octavius
    Mar 18, 2021 at 20:21
  • $\begingroup$ i'm trying to do the second example what if $g = O(f)$ and how i can identify what it is? Can i define f and g as Big O? $\endgroup$
    – leomarrg1
    Mar 18, 2021 at 20:56
  • $\begingroup$ Big O of a function $f$, i.e. $\mathcal{O}(f)$ is a set. Writing something like $g = \mathcal{O}(f)$ is pretty common, but it is abuse of notation. The correct way to write it would be $g \in \mathcal{O}(f)$. So your task is to check whether $g$ is an element of the set. You do this by checking whether $g$ satisfies the necessary conditions. $\endgroup$
    – Octavius
    Mar 18, 2021 at 21:07
  • $\begingroup$ So i could say that $g(n) \leq c * f(n)$ for all $ n \geq n_0$? And that proves that $g \in { O } (f)$? $\endgroup$
    – leomarrg1
    Mar 18, 2021 at 21:29
0
$\begingroup$

From scratch then:

Consider some arbitrary function $f$ and the "Big O" of $f$, i.e. $\mathcal{O}(f)$. This $\mathcal{O}(f)$ is a set, consisting of all functions that satisfy a certain condition. This condition somehow includes $f$. You have already given the definition of $\mathcal{O}(f)$, but I will rewrite it now:

$$\mathcal{O}(f) \enspace = \enspace \Big\{ \; g : \mathbb{N} \longrightarrow \mathbb{R} \; \Big| \; \exists \, c > 0 \; \exists \, n_0 \in \mathbb{N} \; \forall \, n \geq n_0 \; : \; g(n) \leq c \cdot f(n) \; \Big\}$$

In other words, the set $\mathcal{O}(f)$ is a set of functions who map from the natural numbers $\mathbb{N}$ to the real numbers $\mathbb{R}$. These functions have to satisfy a certain condition, namely that there is some constant $c$, which is greater than zero, such that $g(n) \leq c \cdot f(n)$. This inequality does not have to hold for every function value of $g(n)$ and $f(n)$. It only has to hold for all function values after a certain "point" $n_0$. Let us look at an example:


Example: Consider the functions

$$g(n) = n \qquad \text{and} \qquad f(n) = n^2 - n$$

We want to show that $g \in \mathcal{O}(f)$ holds. If we insert $n=1$, we find

$$g(1) = 1 \qquad \text{and} \qquad f(1) = 0$$

But there exists no constant $c > 0$, such that $1 \leq c \cdot 0$. Does this mean, that $g \notin \mathcal{O}(f)$? The answer is NO. Why? Because if we insert $n=2$ or $n=3$ or $n = 4,5,6, \ldots$ we find that for these values the inequality

$$ g(n) \leq c \cdot f(n) $$

is fulfilled when e.g. picking $c = 1$. This means, that when $c = 1$ then for all $n$ that are greater than $n_0 = 1$ we find $g(n) \leq c \cdot f(n)$. However, this is exactly the definition of $\mathcal{O}(f)$. Therefore,

$$g(n) \in \enspace \mathcal{O}(n^2 - n)$$

${}$

Problem 2

Consider now the second problem you have stated. We want to prove that if $g \in \mathcal{O}(f)$ then $f + g \in \Theta(f)$.

How do we do this? First of all, we gather the information we have. In this case, we know that $g \in \mathcal{O}(f)$. By definition, we know that there exists a $c>0$ and a $n_0$ such that for all $n \geq n_0$ the inequality $g(n) \leq c \cdot f(n)$ holds.

Now we simply add $f(n)$ on both sides of the inequality (which we know by assumption to be true). This gives us

$$g(n) + f(n) \leq (c+1) \cdot f(n)$$

This was the first part. Now the second part: $g(n)$ is nonnegative, so we know that $g(n) \geq 0$ and therefore

$$f(n) \leq f(n) + g(n)$$

(because adding something positive to a number always makes the number greater).

We combine these two results and have

$$ f(n) \; \leq \; f(n) + g(n) \; \leq \; (c+1) f(n)$$

This completes the proof that $(f + g) \in \Theta(f)$.

$\endgroup$
1
  • $\begingroup$ Thank you so much, this helped. $\endgroup$
    – leomarrg1
    Mar 19, 2021 at 16:36

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.