# Prove problem

• Nov 28th 2009, 01:05 AM
nesibess
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)$

• Nov 28th 2009, 01:52 AM
tonio
Quote:

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
• Nov 28th 2009, 04:02 AM
nesibess
Quote:

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 (Worried)
• Nov 28th 2009, 04:42 AM
HallsofIvy
What is the definition of "O(f)"?
• Nov 28th 2009, 05:19 AM
tonio
Quote:

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 (Worried)

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
• Nov 28th 2009, 05:44 AM
emakarov
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.
• Nov 28th 2009, 05:56 AM
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 (Crying) Please help me
• Nov 28th 2009, 06:33 AM
tonio
Quote:

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 (Crying) Please help me