Results 1 to 8 of 8

Math Help - Prove problem

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    6

    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) f\in O(g)
    b) g\in O(f)

    Thank you for your attentions.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by nesibess View Post
    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) f\in O(g)
    b) g\in O(f)

    Thank you for your attentions.

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

    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:

    \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. \Longrightarrow\,f=O (g)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    6
    Quote Originally Posted by tonio View Post
    f(n)=\left\{\begin{array}{cc}2&\,\mbox { if }n\mbox{ is even}\\1&\,\mbox { if }n\mbox{ is odd}\end{array}\right.

    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:

    \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. \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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,696
    Thanks
    1467
    What is the definition of "O(f)"?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by nesibess View Post
    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  f=O(g)\mbox{ as }x\rightarrow a\mbox{ if }\exists\mbox{ constant }M\mbox{ s.t. }|f(x)|\leq M|g(x)| \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 f=O(g) meaning this is true when n\rightarrow \infty , but you should, of course, check your own definition.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2009
    Posts
    6
    If I am wrong, Please tell me.

    My solution is:

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

    b) 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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by nesibess View Post
    If I am wrong, Please tell me.

    My solution is:

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

    b) 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

    Read what's been answered to you and/or re-read your book carefully. All is there.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 22nd 2009, 03:17 AM
  2. prove problem 2
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: August 5th 2009, 08:12 AM
  3. Replies: 2
    Last Post: October 30th 2007, 02:10 PM
  4. prove problem
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 18th 2006, 05:27 AM
  5. how to prove this problem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: May 20th 2005, 03:47 AM

Search Tags


/mathhelpforum @mathhelpforum