1. ## Prove problem

Hi everybody. I need a help about prove. My question is

Let f,g: Z ->R where

f(n)= {2, for n even and 1,for n odd}
g(n) ={3,for n even and 4,for n odd}

Prove or disprove each of the following

a)$\displaystyle f\in O(g)$
b)$\displaystyle g\in O(f)$

2. Originally Posted by nesibess
Hi everybody. I need a help about prove. My question is

Let f,g: Z ->R where

f(n)= {2, for n even and 1,for n odd}
g(n) ={3,for n even and 4,for n odd}

Prove or disprove each of the following

a)$\displaystyle f\in O(g)$
b)$\displaystyle g\in O(f)$

$\displaystyle f(n)=\left\{\begin{array}{cc}2&\,\mbox { if }n\mbox{ is even}\\1&\,\mbox { if }n\mbox{ is odd}\end{array}\right.$

$\displaystyle g(n)=\left\{\begin{array}{cc}3&\,\mbox { if }n\mbox{ is even}\\4&\,\mbox { if }n\mbox{ is odd}\end{array}\right.$ , so for example:

$\displaystyle \frac{f(n)}{g(n)}=\left\{\begin{array}{cc}\frac{2} {3}&\,\mbox { if }n\mbox{ is even}\\{}\\\frac{1}{4}&\,\mbox { if }n\mbox{ is odd}\end{array}\right.$ $\displaystyle \Longrightarrow\,f=O (g)$

Tonio

3. Originally Posted by tonio
$\displaystyle f(n)=\left\{\begin{array}{cc}2&\,\mbox { if }n\mbox{ is even}\\1&\,\mbox { if }n\mbox{ is odd}\end{array}\right.$

$\displaystyle g(n)=\left\{\begin{array}{cc}3&\,\mbox { if }n\mbox{ is even}\\4&\,\mbox { if }n\mbox{ is odd}\end{array}\right.$ , so for example:

$\displaystyle \frac{f(n)}{g(n)}=\left\{\begin{array}{cc}\frac{2} {3}&\,\mbox { if }n\mbox{ is even}\\{}\\\frac{1}{4}&\,\mbox { if }n\mbox{ is odd}\end{array}\right.$ $\displaystyle \Longrightarrow\,f=O (g)$

Tonio
I beg to you, you can explain more. Beacuse I have learnt this topic yet. And I want to learn deeply

4. What is the definition of "O(f)"?

5. Originally Posted by nesibess
I beg to you, you can explain more. Beacuse I have learnt this topic yet. And I want to learn deeply

According to definition, for two functions f,g we have that $\displaystyle f=O(g)\mbox{ as }x\rightarrow a\mbox{ if }\exists\mbox{ constant }M\mbox{ s.t. }|f(x)|\leq M|g(x)|$ $\displaystyle \Longleftrightarrow\left|\frac{f(x)}{g(x)}\right|\ leq M\mbox{ whenever }|x-a|<\delta\,,\mbox{ for some }\delta>0$

In your case (and in most cases with arithmetic functions), we usually shorten the above and say $\displaystyle f=O(g)$ meaning this is true when $\displaystyle n\rightarrow \infty$ , but you should, of course, check your own definition.

Tonio

6. Imagine that g(n) is your salary during the nth month and f(n) is the salary of the head of the company where you work. If f(n) is O(g(n)), then, even though your boss ma earn, say, between 2 and 100 more then you, this ratio stays within these limits as time goes. But when f(n) is not O(g(n)), it means that the ratio increases indefinitely with time. It does not have to increase monotonically. Say, for n=1, 2, 3, 4, 5, 6, 7, 8 ..., the ratio f(n)/g(n) can be 5, 50, 10, 60, 15, 70, 20, 80, ... etc. If this continues, this will lead to social tension, possibly strikes and all kinds of problems in the society.

In your case, since neither function grows indefinitely compared to the other, both are big-O of each other.

7. If I am wrong, Please tell me.

My solution is:

a)$\displaystyle f\in O(g)$ => f(n)<C.g(n) if n=even 2<C.3 OR if n=odd 1<C.4

b)$\displaystyle g\in O(f)$ => g(n)<C.f(n) if n=even 3<C.2 OR if n=odd 4<C.2
is it correct? or I don't know anything this topic is hard for me Please help me

8. Originally Posted by nesibess
If I am wrong, Please tell me.

My solution is:

a)$\displaystyle f\in O(g)$ => f(n)<C.g(n) if n=even 2<C.3 OR if n=odd 1<C.4

b)$\displaystyle g\in O(f)$ => g(n)<C.f(n) if n=even 3<C.2 OR if n=odd 4<C.2
is it correct? or I don't know anything this topic is hard for me Please help me