Results 1 to 4 of 4

Math Help - Finding Big Oh

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    14

    Finding Big Oh

    I'm trying to calculate the big oh for something

    f(N) = .00001 * N^2 + .01*N + 1
    g(N) = 4*log2(N)

    What's the Big Oh for f and g?

    What values of N are best for f(N) and g(N)

    What does this tell you about using Big OH to decided which algorithm to use?

    ----------

    I haven't done a whole lot with big Oh, but this is a sample problem from an old test i'm practicing off. Any help would be great.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2007
    From
    Melbourne
    Posts
    428
    O(f) = N^2
    O(g) = log N

    The largest power of N in a polynomial is always its big Oh notation

    Any function containing just a logarithm has O(log N).

    To find which algorithm is best for which values of N, the simplest way is probably just to solve f(N) = g(N) and then test a number in each interval between the solutions to find out which is better in that interval.

    What does this tell you about using Big OH to decided which algorithm to use?
    They probably want you to say that it is only useful for large values of N.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2007
    Posts
    14
    thanks.

    so, for example, f(N) N^5 + N^2 + 7log(N) will still have a big Oh of N^5? Or does the log negate something
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Eclyps19 View Post
    thanks.

    so, for example, f(N) N^5 + N^2 + 7log(N) will still have a big Oh of N^5? Or does the log negate something
    log(N) grows more slowly than any positive power of N, so N^5 + N^2 + 7log(N) is O(N^5)

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: December 8th 2011, 10:27 AM
  2. Replies: 1
    Last Post: July 3rd 2010, 10:40 PM
  3. Finding a limit. Finding Maclaurin series.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 18th 2010, 10:04 PM
  4. Finding the radius, solving, and finding theta?
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: June 13th 2009, 02:37 PM
  5. Replies: 1
    Last Post: April 9th 2009, 09:02 AM

Search Tags


/mathhelpforum @mathhelpforum