Results 1 to 7 of 7

Math Help - Need help with Growth of Functions questions

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Need help with Growth of Functions questions

    I've never really gotten the hang of algorithms and the like, so I could really use a hand with these.

    Here's the question, word for word. Be sure to show your work.

    Determine whether or not the following are true. Provide a derivation showing why or why not. For convenience, you may assume that the logs are in the base of your choice, but you should specify what base you are using in your derivation.

    a) 99 is \Theta(1)

    b) 6n^3-3n^2\log n-6n^2+11n\log n is \Omega(n^3)

    c) 7n^2-19n+32 is O(n^3)

    d) n^5/44 -3n^4 is \Theta(n^4)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2010
    Posts
    29
    Quote Originally Posted by Runty View Post
    I've never really gotten the hang of algorithms and the like, so I could really use a hand with these.

    Here's the question, word for word. Be sure to show your work.

    Determine whether or not the following are true. Provide a derivation showing why or why not. For convenience, you may assume that the logs are in the base of your choice, but you should specify what base you are using in your derivation.

    a) 99 is \Theta(1)

    b) 6n^3-3n^2\log n-6n^2+11n\log n is \Omega(n^3)

    c) 7n^2-19n+32 is O(n^3)

    d) n^5/44 -3n^4 is \Theta(n^4)
    c) 7n^2-19n+32 is O(n^3)

    Definition of big O notation:

    f(x)=O(g(x)) \text{ as } x\to\infty\, if and only if there exists a positive real number M and a real number x_0 such that
    |f(x)| \le M |g(x)| \text{ for all }x>x_0.

    Let f(x) = 7x^2-19x+32, g(x) = x^3. For x = 10, f(x) = 542, g(x) = 1000, and since f(x) \le g(x) \text{ for all }x>10, take x_0 = 10, M = 1 and you've proved 7n^2-19n+32 is O(n^3).

    The rest of these are really similar. Put in the definitions and find some constants that satisfy the definition. Let me know if you have questions about any one of the four definitions or need another example.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    29
    Quote Originally Posted by lgstarn View Post
    Let me know if you have questions about any one of the four definitions or need another example.
    By four definitions I mean Omega, little o, big O, or Theta.
    Last edited by lgstarn; February 11th 2010 at 10:25 AM. Reason: Correcting typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jan 2010
    Posts
    232
    Quote Originally Posted by lgstarn View Post
    c) 7n^2-19n+32 is O(n^3)

    Definition of big O notation:

    f(x)=O(g(x)) \text{ as } x\to\infty\, if and only if there exists a positive real number M and a real number x_0 such that
    |f(x)| \le M |g(x)| \text{ for all }x>x_0.

    Let f(x) = 7x^2-19x+32, g(x) = x^3. For x = 10, f(x) = 542, g(x) = 1000, and since f(x) \le g(x) \text{ for all }x>10, take x_0 = 10, M = 1 and you've proved 7n^2-19n+32 is O(n^3).

    The rest of these are really similar. Put in the definitions and find some constants that satisfy the definition. Let me know if you have questions about any one of the four definitions or need another example.
    SECOND EDIT: Ugh, I just can't be sure whether or not this would truly work. The main problem is either my sources not explaining themselves or me misinterpreting the examples I'm finding. I still need help on these.
    Last edited by Runty; February 11th 2010 at 11:35 AM. Reason: Need more detail
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    29
    Quote Originally Posted by Runty View Post
    a) 99 is \Theta(1)
    Definition of \Theta

    f(x)=\Theta(g(x)) \text{ as } x\to\infty\, if and only if there exists positive real numbers k_1 and k_2 and a positive real number x_0 such that

    k_1|g(x)| \le |f(x)| \le k_2 |g(x)| \text{ for all }x>x_0

    f(x) = 99, g(x) = 1

    Thus k_1 = 98, k_2 = 100 for any x_0, say x_0 = 42.

    Quote Originally Posted by Runty View Post
    b) 6n^3-3n^2\log n-6n^2+11n\log n is \Omega(n^3)
    f(x)=\Omega(g(x)) \text{ as } x\to\infty\, if and only if there exists s positive real number k_1 and a positive real number x_0 such that

    k_1|g(x)| \le |f(x)| \text{ for all }x>x_0

    f(x) = 6n^3-3n^2\log n-6n^2+11n\log n

    g(x) = n^3

    f(10) = 5353.28
    g(10) = 1000

    We can now see that f(x) is growing faster than g(x) for x > 10. It is probably enough to just say that because it is pretty obvious if you look at it. But if your teacher is feeling pedantic, you can try to show it in a couple of ways.

    Way number 1: plot the function h(x) = f(x) - g(x) = 5x^3-3x^2\log x-6x^2+11x\log x and show it is always positive for x > 2. Thus, f(x) grows faster than g(x). But maybe your teacher doesn't like a graphical "proof."

    Way number 2: Consider \lim_{x \rightarrow \infty} \frac{6x^3-3x^2\log x-6x^2+11x\log x}{x^3} = 6, thus f(x) asymptotically grows 6 times faster than g(x). But maybe your teacher will say, but how do you know that is valid for x > 10 and not x > 100?

    Way number 3: Call h(x) = f(x) - g(x) and compute h'(x) = 15x(x-1) + (11 -6x)\log(x) + 11. Notice that \log(x) grows really slowly (say it is \log_{10}(x), so \log_{10}(10) = 1), and so clearly h'(x) > 0 for x > 10. So h(x) is growing, and thus f(x) is growing faster than g(x). But again I relied on the fact that one function is 'clearly' growing faster than another.

    Anyways, I doubt your teacher wants you to go to this level of detail unless it is an excessively mathematical class. Just saying it grows faster should be enough.

    While this stuff looks complicated, it is actually really simple. You can use this ordering to get a really intuitive feel for this:

    Big O notation - Wikipedia, the free encyclopedia

    to quickly understand which functions grow from slowest to fastest, from a constant all the way up to factorials and iterated exponential.

    So anyways, why don't you give n^5/44 -3n^4 is \Theta(n^4) a try for yourself?
    Last edited by lgstarn; February 11th 2010 at 05:05 PM. Reason: correcting typo
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jan 2010
    Posts
    232
    I feel I should iterate: for solving these, you must use either the inequalities method or the limits method.

    I suppose your answers could work, but I feel as though I need a second opinion.

    EDIT: Also, I feel I could use some help on the last one, n^5/44 -3n^4. I know it's not \Theta(n^4), but I could use some help with a proof.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2010
    Posts
    12
    Quote Originally Posted by lgstarn View Post
    c) 7n^2-19n+32 is O(n^3)

    Definition of big O notation:

    f(x)=O(g(x)) \text{ as } x\to\infty\, if and only if there exists a positive real number M and a real number x_0 such that
    |f(x)| \le M |g(x)| \text{ for all }x>x_0.

    Let f(x) = 7x^2-19x+32, g(x) = x^3. For x = 10, f(x) = 542, g(x) = 1000, and since f(x) \le g(x) \text{ for all }x>10, take x_0 = 10, M = 1 and you've proved 7n^2-19n+32 is O(n^3).

    The rest of these are really similar. Put in the definitions and find some constants that satisfy the definition. Let me know if you have questions about any one of the four definitions or need another example.

    I get that from that equation the big O would be n^2  could you future elaborate how big o is O(n^3)
    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: October 14th 2010, 04:25 AM
  2. growth rate of functions
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 13th 2009, 07:33 PM
  3. Exponential growth and decay questions (2)
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 3rd 2009, 10:21 PM
  4. Big O and Growth of Functions
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 8th 2008, 01:15 AM
  5. The Growth of Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 13th 2006, 12:09 AM

Search Tags


/mathhelpforum @mathhelpforum