Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Arrange the following 9 functions based on the incremental nature

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    athens
    Posts
    5

    Arrange the following 9 functions based on the incremental nature

    Hello everyone..this is a part of an exercise on Algorithms and Complexity.
    Arrange the following 9 functions based on the incremental nature(for example x^2 + 3x + 4. we will only use the x^2), if the
    function f (n) is immediately before the function g (n) in order, should apply f (n) =
    O (g (n)).

    And here is the functions...
    f1 = 2n+ n√n
    f2 = 3^(log2n) 2 is the base but i don't know how to write it smaller.
    f3 = 4^n
    f4 = 4logn
    f5 = (log(n!))^2
    f6 = n^(2/3)
    [logn]
    f7 = Σi
    i=1
    f8 = (n^2)(3^n)
    f9 = (5/6)^n

    my thought is that f4 f5 and f7 are logarithm functions which are increasing slower than the other.
    from these 3 f7 seems slower,after f4 and after this f5

    f1 f6 are polynomial(faster than logarithm slower than exponential) and from them, f6 is the slower
    so till now it should be like this f7 f4 f5 f6 f1

    f3 f8 and f9 are exponential so they increase faster than the other.
    About f9 (5/6)<1 so i am trying to find where it fits.. f8 is slower than f3

    so till now it should be like f7 f4 f5 f6 f1 f8 f3

    I am not sure where is the place for f9 and f2. and what it is exactly...logarithm or polynomial :S
    Last edited by SmartMonkey; December 17th 2012 at 02:13 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Arrange the following 9 functions based on the incremental nature

    Not all exponential functions increase faster than polynomial. In this case, f9 is the only function out of nine that tends to zero rather than infinity.

    Second, not every function that starts with log grows like a logarithm. We have \log n!=\log(1\cdot\ldots\cdot n)=\log1+\dots+\log n\le n\log n. This is the upper bound. For the lower bound we can use Stigling's approximation n!\ge\sqrt{2\pi}\ n^{n+1/2}e^{-n}, from where \log n!\ge (n+1/2)\log n-n\log e+C for some C, and this is \ge (1/2)n\log n from some point. So, \log n!=O(n\log n) and n\log n\le \log n!, i.e., \log n!=\Theta(n\log n). In particular, \log n! grows faster than n^{2/3}.

    Since 3=2^{\log_23}, we have f_2(n) = 3^{\log_2n}=\left(2^{\log_23}\right)^{\log_2n} = 2^{\log_23\cdot\log_2n} = \left(2^{\log_2n}\right)^{\log_23} = n^{\log_23} and \log_23=\ln 3/\ln 2\approx1.58. So, f_2(n) grows faster than f_1(n)=O(n^{1.5}).
    Thanks from SmartMonkey
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2012
    From
    athens
    Posts
    5

    Re: Arrange the following 9 functions based on the incremental nature

    That was really helpfull. Just to be sure this is the answear right? 9 7 4 6 5 1 2 8 3
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Arrange the following 9 functions based on the incremental nature

    Concerning f7, \sum_i^ni=O(n^2), so f_7(n)=O((\log n)^2), which grows faster than f_4(n)=4\log n.
    Thanks from SmartMonkey
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2012
    From
    athens
    Posts
    5

    Re: Arrange the following 9 functions based on the incremental nature

    That was so helpfull. you made everything much clearer.. sorry for my english
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Incremental increase in ratios.
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: July 2nd 2012, 06:34 AM
  2. Accounting - Incremental Analysis
    Posted in the Business Math Forum
    Replies: 2
    Last Post: July 4th 2010, 06:16 PM
  3. [SOLVED] Θ-classes to arrange functions?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 22nd 2010, 06:33 AM
  4. Formulating Incremental Commission
    Posted in the Business Math Forum
    Replies: 1
    Last Post: October 12th 2009, 08:21 AM
  5. Replies: 4
    Last Post: June 25th 2007, 09:14 AM

Search Tags


/mathhelpforum @mathhelpforum