Results 1 to 8 of 8

Math Help - Theta notation

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    7

    Theta notation

    Hi peoples,

    I have a problem with theta notations and was wondering if anyone could give me a hand?

    The question is:

    4nlgn + n + 6

    Where I have to select the theta notation and justify my answer.

    Many thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by madmunk View Post
    Hi peoples,

    I have a problem with theta notations and was wondering if anyone could give me a hand?

    The question is:

    4nlgn + n + 6

    Where I have to select the theta notation and justify my answer.

    Many thanks.
    f(n) \in \Theta(g(n)) \textbf{ iff }\exists (C,C'>0), n_0 : \forall (n>n_0) \; |Cg(n)| < |f(n)| < |C'g(n)|

    I claim 4n\log n + n + 6 \in \Theta(n\log n), can you find C and C', such that the definition holds?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    7
    Thanks Isomorphism,

    But unfortunately, what you wrote has meant nothing to me. I can't figure out what you have written. Would you mind if you 'dumb' it down for me please?

    Thanks
    MadMunk
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2007
    Posts
    17
    I'm not really getting your question.. are you talkin about functions growth here.. ?? Omega and big-O and these kind of things..?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by MMM88 View Post
    I'm not really getting your question.. are you talkin about functions growth here.. ?? Omega and big-O and these kind of things..?
    Yes I think he means that...

    Quote Originally Posted by madmunk View Post
    Thanks Isomorphism,

    But unfortunately, what you wrote has meant nothing to me. I can't figure out what you have written. Would you mind if you 'dumb' it down for me please?

    Thanks
    MadMunk

    Hmm what is your definition of Theta function?

    In simple words, I am saying that 4nlgn+n+6 has the same growth rate as nlogn.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2007
    Posts
    17
    Alright, in order to show that a specific funtion is (theta) some other function, we have to check the big-O and Omega notations first.

    In other words..

    If we have f(n) = n - 27 as our function and we need to show whether f(n) is theta (log n) for instance. Then first we have to show that f(n) is omega (log n) and f(n) is big-o (log n) at the same time. If those two derivations apply to the fucntion then we can say that f(n) IS theta (log n).
    If one of them fails then f(n) is not theta (log n).
    I'm not sure if it makes sense to you here or even if this what you mean by your question. The question is not clear.. whats the fucntion that were supposed to be basing our first fucntion(the one you mentioned) on ??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by MMM88 View Post
    Alright, in order to show that a specific funtion is (theta) some other function, we have to check the big-O and Omega notations first.

    In other words..

    If we have f(n) = n - 27 as our function and we need to show whether f(n) is theta (log n) for instance. Then first we have to show that f(n) is omega (log n) and f(n) is big-o (log n) at the same time. If those two derivations apply to the fucntion then we can say that f(n) IS theta (log n).
    If one of them fails then f(n) is not theta (log n).
    I'm not sure if it makes sense to you here or even if this what you mean by your question. The question is not clear.. whats the fucntion that were supposed to be basing our first fucntion(the one you mentioned) on ??
    Hmm I am quite confused. Are you telling me or the original poster?

    Because I am pretty sure the answer is nlogn
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2007
    Posts
    17
    Quote Originally Posted by Isomorphism View Post
    Hmm I am quite confused. Are you telling me or the original poster?

    Because I am pretty sure the answer is nlogn
    No, I was actually talking to the one who made the thread.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help~~about the theta notation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 29th 2009, 01:11 AM
  2. Theta Notation for Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 10th 2008, 12:25 AM
  3. little oh notation and theta
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 3rd 2007, 09:30 PM
  4. Find theta notation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2007, 05:56 AM
  5. Theta notation for functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:54 AM

Search Tags


/mathhelpforum @mathhelpforum