Order by asymptotic growth rate

Click For Summary
SUMMARY

The discussion centers on comparing the asymptotic growth rates of the functions f(n) = (n+1)! and g(n) = n^{logn}. The user correctly identifies that to determine which function grows faster, one must evaluate the limit lim_{n→∞} (f(n)/g(n)). The conclusion drawn is that if this limit approaches zero, g(n) grows faster; if it approaches infinity, f(n) grows faster. The user expresses uncertainty about calculating the limit involving the factorial function and the logarithmic expression.

PREREQUISITES
  • Understanding of asymptotic notation and growth rates
  • Familiarity with limits in calculus
  • Knowledge of factorial functions and their properties
  • Basic understanding of logarithmic functions and their transformations
NEXT STEPS
  • Learn techniques for evaluating limits involving factorials, such as Stirling's approximation
  • Study the properties of logarithmic functions and their applications in asymptotic analysis
  • Explore the concept of exponential growth versus polynomial growth in depth
  • Practice problems on comparing growth rates of various functions using limits
USEFUL FOR

Students in computer science or mathematics, particularly those studying algorithms and complexity theory, as well as anyone interested in understanding function growth rates and limits.

dba
Messages
29
Reaction score
0

Homework Statement


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

f(n)= (n+1)! and g(n)=n^{logn}

Homework Equations


\lim_{n\to\infty}\frac{f(n)}{g(n)} = 0

then g(n) is faster growing.

\lim_{n\to\infty}\frac{f(n)}{g(n)} = \infty

then f(n) is faster growing.

The Attempt at a Solution


I would guess that n^{logn} is the faster growing function because it is exponential.
Thus, I write
\lim_{n\to\infty}\frac{(n+1)!}{n^{logn}} 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
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,
log_{10}n = x
implies
n = 10^x

I hope it helps at least[/STRIKE]
 

Similar threads

Replies
3
Views
3K
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 21 ·
Replies
21
Views
1K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 2 ·
Replies
2
Views
3K