1
$\begingroup$

Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?

My idea: i think because of for any $f:N\rightarrow N$, and $g:N\rightarrow N$ then $f(n)+g(n)= O(\max \{f(n),g(n)\})$ then there are no two such functions. is my argument is valid?

Improve this question
$\endgroup$
1
  • $\begingroup$ Well, you can construction an example by choosing $f$ and $g$ such that the function $\max(f,g)$ is never equal to only one of $f$ or $g$ for sufficiently large input $n$. For example, suppose that $f(n)=n$ for $n$ even and equal to $0$ otherwise, and define $g(n)=n$ for $n$ odd and equal to $0$ otherwise. Then $(f+g)(n)=n$ for all $n$, but it can't be in either $O(f)$ or $O(g)$. This is because any function in $O(f)$ is forced to be equal to $0$ for all sufficiently large odd inputs. Similarly, all functions in $O(g)$ must be zero for all sufficiently large even inputs. $\endgroup$
    – plop
    Commented Mar 8, 2021 at 16:43

1 Answer 1

Reset to default
1
$\begingroup$

Let $f(n) = \begin{cases} 1 & \mbox{if $n$ is odd}\\ n & \mbox{if $n$ even} \end{cases}$, and $g(n) = \begin{cases} n & \mbox{if $n$ is odd}\\ 1 & \mbox{if $n$ even} \end{cases}$.

Then, $h(n)=f(n)+g(n) = n+1 \not\in O(f(n))$.

Indeed, for any $n_0$ and $c>0$, there is some $n \ge n_0$ such that $h(n) > c f(n)$. Simply pick $n$ as an odd integer greater than $\max\{c, n_0\}$, e.g., $n=2\max\{c, n_0\}+1$. Then $h(n) = n+1 = 2\max\{c, n_0\} + 2 > c = c \cdot 1 = c f(n)$.

A similar argument shows that $h(n) \not\in O(g(n))$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Excuse me, i want simultaneous, $h(n)\notin O(f(n))$ and $h(n)\notin O(g(n))$, but with your above argument $h(n)\in O(g(n))$. $\endgroup$
    – user132812
    Commented Mar 8, 2021 at 17:09
  • $\begingroup$ @MohammadRostami You won't be able to have $h\in O(g)$. Look at what happens for $n$ even and large enough. The inequality $|h(n)|\leq c|g(n)|$ becomes $n+1\leq c$. $\endgroup$
    – plop
    Commented Mar 8, 2021 at 17:16
  • $\begingroup$ thanks, its very helpful:) $\endgroup$
    – user132812
    Commented Mar 8, 2021 at 17:20

Your Answer

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