Ok so the problem I am interested in is $f(n) \not\in Og(n)$ and $g(n) \not\in Of(n)$ dealing with natural numbers into positive reals, ($\mathbb{N}$ $\rightarrow$ $\mathbb{R+}$ )

O is a comparison operator, and for some functions f and g we can say that f = O(g) or vice-versa. But there exist f and g where neither f = O(g) or g = O(f) holds.

My first thought was that this is true when

 f(odd number n) = 1
 f(even number n) = 2^n
 g(odd number n) = 2^n
 g(even number n) = 1

Which I still believe that it does. But I don't know how to express this in mathematical terms. Also, i received heavy criticism about it and was told that there are INFINITELY many simple examples where this is true. Only problem is, they cant be that simple (Or im having a brain fart) if i can't even think of another one!

Im not asking for an answer, but rather some help. Could somebody explain to me why and how to approach this problem if it really is as easy is I keep being told?

Also if anyone could explain to me how to put my answer into mathmatical term, that would be greatly appericated. (I think it has something to do with Sin(x) or maybe some number raised to the power of sin, but I am not sure.)

Thank You all in advance for your answers!


Your example is fine. The functions $f$ and $g$ can be described as follows:

$$\begin{align*} &f:\Bbb N\to\Bbb R:n\mapsto \begin{cases} 1,&\text{if }n\text{ is odd}\\ 2^n,&\text{if }n\text{ is even} \end{cases}\\\\ &g:\Bbb N\to\Bbb R:n\mapsto \begin{cases} 2^n,&\text{if }n\text{ is odd}\\ 1,&\text{if }n\text{ is even} \end{cases} \end{align*}$$

One easy way to get infinitely many examples is by simple variations of this model: you can replace $1$ by any bounded function of $n$ and $2^n$ by any unbounded function of $n$. If $A$ is an infinite subset of $\Bbb N$ such that $\Bbb N\setminus A$ is also infinite, you can replace n is odd by $n\in A$ and n is even by $n\notin A$.


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.