Results 1 to 6 of 6

Math Help - Big Oh and Big Omega

  1. #1
    Newbie
    Joined
    Jan 2008
    From
    Boise
    Posts
    16

    Big Oh and Big Omega

    Here is a problem I'm having trouble with:

    Find big Oh and big Omega of log(n!)

    I have tried Stirling's formula but I'm not sure that this is a satisfactory approach.

    Any suggestions/help would be appreciated.

    Thanks in advance.

    The other problem is to solve the recurrence relation

    T(n) = 3T(n/4)+n

    I simply cannot see the approach required here to solve this.
    Again any help would be appreciated.
    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 Ian Moore View Post
    The other problem is to solve the recurrence relation

    T(n) = 3T(n/4)+n

    I simply cannot see the approach required here to solve this.
    Again any help would be appreciated.
    Master theorem - Wikipedia, the free encyclopedia is a wonderful tool. You should learn it up.

    The answer using masters theorem would be O(n)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2008
    From
    Boise
    Posts
    16
    Thanks for the reference. Greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2008
    From
    Boise
    Posts
    16
    Incidentally, do you have any suggestions about the first problem posed ?
    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 Ian Moore View Post
    Here is a problem I'm having trouble with:

    Find big Oh and big Omega of log(n!)

    I have tried Stirling's formula but I'm not sure that this is a satisfactory approach.
    It is a valid approach.

    Alternatively observe that:

    [\forall i \in \mathbb{N}: 2 < i <n] , \log 2 < \log i < \log n

    This implies \log(n!) \in O(n\log n) and \log(n!) \in \Omega(n)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2008
    From
    Boise
    Posts
    16
    Thankyou for your reply on Big O and Big Omega of log(n!).
    You say that log(n!) is an element of Big Omega of n.

    I would have thought that it is the same as Big Oh, i.e.
    log(n!) = O(nlog(n)) and log(n!) = Omega(nlog(n))

    Surely this is a consequence of Stirlings formula ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 25th 2011, 09:46 AM
  2. Big Omega question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 20th 2009, 10:06 AM
  3. dimensions of omega
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: May 19th 2008, 03:59 AM
  4. Omega
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 20th 2008, 01:09 PM
  5. Angular Velocity (Omega)
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 6th 2007, 03:49 AM

Search Tags


/mathhelpforum @mathhelpforum