LinkBack URL
About LinkBacksHi 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)
b)
Thank you for your attentions.
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)
b)
Thank you for your attentions.
, so for example:
}{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.)
Tonio
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\mbox{ as }x\rightarrow a\mbox{ if }\exists\mbox{ constant }M\mbox{ s.t. }|f(x)|\leq M|g(x)|)
In your case (and in most cases with arithmetic functions), we usually shorten the above and saymeaning this is true when
, but you should, of course, check your own definition.
Tonio
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.
If I am wrong, Please tell me.
My solution is:
a)=> f(n)<C.g(n) if n=even 2<C.3 OR if n=odd 1<C.4
b)=> 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 mePlease help me
Read what's been answered to you and/or re-read your book carefully. All is there.
Tonio
  |
