Results 1 to 2 of 2

Thread: Big O and Growth of Functions

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    3

    Big O and Growth of Functions

    Hey I can't figure this HW assignment out, could anyone help me solve this...it would greatly be appreciated.

    Find the least integer $\displaystyle n$ such that $\displaystyle f(x)$ is $\displaystyle O(x^n)$ for each of these functions.

    a) $\displaystyle f(x) = 2x^2+x^3logx$
    b) $\displaystyle f(x) = 3x^5+(logx)^4$
    c) $\displaystyle f(x) = (x^4+x^2+1)/(x^4+1)$
    d) $\displaystyle f(x) = (x^3+5logx)/(x^4+1)$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by Dharper07 View Post
    Hey I can't figure this HW assignment out, could anyone help me solve this...it would greatly be appreciated.

    Find the least integer $\displaystyle n$ such that $\displaystyle f(x)$ is $\displaystyle O(x^n)$ for each of these functions.

    a) $\displaystyle f(x) = 2x^2+x^3logx$
    b) $\displaystyle f(x) = 3x^5+(logx)^4$
    c) $\displaystyle f(x) = (x^4+x^2+1)/(x^4+1)$
    d) $\displaystyle f(x) = (x^3+5logx)/(x^4+1)$
    First do you have a definition of what:

    $\displaystyle f(x)=O(x^n)$

    means?

    It means that there exists a positive constant $\displaystyle k$ there exists an $\displaystyle x_0$ such that for all $\displaystyle x>x_0$

    $\displaystyle |f(x)|<k |x^n|$

    a) $\displaystyle f(x) = 2x^2+x^3\log(x)$

    Here clearly there is no $\displaystyle k$ such that eventualy:

    $\displaystyle
    |2x^2+x^3\log(x)|<k|x^3|
    $

    since $\displaystyle \log(x)$ also grows without bound. But as $\displaystyle \log(x)$ growns more slowly than $\displaystyle x$ (that is $\displaystyle \lim_{x \to \infty} \log(x)/x =0$) we can find $\displaystyle k$ such that:

    $\displaystyle
    |2x^2+x^3\log(x)|<k|x^4|
    $

    So the least integer $\displaystyle n$ such that:

    $\displaystyle 2x^2+x^3\log(x)=O(x^n)$

    is $\displaystyle 4$

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Comparing growth of functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 14th 2010, 03:25 AM
  2. growth rate of functions
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Nov 13th 2009, 06:33 PM
  3. Growth of Functions Problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 3rd 2008, 05:29 PM
  4. Growth Functions - Analysis
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: May 18th 2006, 02:16 AM
  5. The Growth of Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 12th 2006, 11:09 PM

Search Tags


/mathhelpforum @mathhelpforum