Order by asymptotic growth rate

In summary, the problem is to evaluate the growth rate of two given functions, (n+1)! and n^{logn}, and determine which is faster growing. The equations for finding the limit of the ratio of the two functions are provided, and the conclusion is that n^{logn} is the faster growing function. The poster also suggests looking at the functions from a different perspective, using the definition of logarithms.
  • #1
dba
32
0

Homework Statement


I try to order given functions and I am stuck with evaluating the following:

[itex]f(n)= (n+1)![/itex] and [itex]g(n)=n^{logn}[/itex]

Homework Equations


[itex]\lim_{n\to\infty}\frac{f(n)}{g(n)} = 0 [/itex]

then g(n) is faster growing.

[itex]\lim_{n\to\infty}\frac{f(n)}{g(n)} = \infty[/itex]

then f(n) is faster growing.

The Attempt at a Solution


I would guess that [itex]n^{logn}[/itex] is the faster growing function because it is exponential.
Thus, I write
[itex]\lim_{n\to\infty}\frac{(n+1)!}{n^{logn}}[/itex] and would expect the result to be zero.

My problem is that I do not know hot to take the limit of a factorial function and I also have a problem with the n^logn.
Can someone help me with this? Maybe I can write the functions in a different way?

Thanks for any help.
 
Physics news on Phys.org
  • #2
Edit: Nevermind. Now I'm curious though.

[STRIKE]I might just be going out on a limb here, but I think that looking at it from this perspective might help:

By the definition of logarithm,
[itex]log_{10}n = x[/itex]
implies
[itex]n = 10^x[/itex]

I hope it helps at least[/STRIKE]
 

What is an asymptotic growth rate?

An asymptotic growth rate is a way to measure the rate at which a function or algorithm grows as its input size increases towards infinity. It is often denoted as "Big O" notation, and it describes the upper bound of the function's growth rate.

Why is it important to understand the asymptotic growth rate?

Understanding the asymptotic growth rate of a function or algorithm allows us to analyze its efficiency and performance. It helps us determine how the algorithm will behave with larger inputs, and can guide us in making decisions about which algorithm to use in a given situation.

How is the asymptotic growth rate calculated?

The asymptotic growth rate is calculated by looking at the dominant term in a function's expression. For example, if a function has a term that grows at a rate of n^2 and another term that grows at a rate of n, the asymptotic growth rate would be O(n^2) because the n^2 term dominates the growth as n approaches infinity.

What is the difference between best-case, worst-case, and average-case asymptotic growth rates?

The best-case asymptotic growth rate refers to the minimum amount of time or resources an algorithm will take to solve a problem. The worst-case asymptotic growth rate refers to the maximum amount of time or resources an algorithm will take. The average-case asymptotic growth rate is an average of all possible inputs and their corresponding growth rates.

Can two algorithms with different asymptotic growth rates have the same performance?

No, two algorithms with different asymptotic growth rates cannot have the same performance. The asymptotic growth rate directly relates to the performance and efficiency of an algorithm, so a lower growth rate will always result in better performance. However, in some cases, two algorithms may have the same asymptotic growth rate, making it important to also consider other factors such as constant factors and practicality in real-world scenarios.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
477
Replies
0
Views
315
Replies
2
Views
790
Replies
2
Views
388
  • Calculus and Beyond Homework Help
Replies
6
Views
391
  • Calculus and Beyond Homework Help
Replies
3
Views
418
Replies
4
Views
295
Replies
4
Views
751
  • Topology and Analysis
Replies
4
Views
275
Back
Top