# Function Growth Rates

• Oct 4th 2006, 07:24 PM
hotmail590
Function Growth Rates
Hello I am trying to figure out what is the growth rates for some fucntions.
So far I only know the order for the basic functions but I would also like to know where would some special/different fucntions would fit

From textbook:

Constant, logN, logn^2, N, NlogN, N^2, N^3 and 2^N (right side growing the fastest)

I would like to know where would the following fucntions fit

N^(1/2), loglogN, N / logN, (1/3)^N, (3/2)^N

Here is my guess,

When N is small such as using N=2

Constant, loglogN, N, N^(1/2), logn^2, logN, N, NlogN, (1/3)^N, (3/2)^N, N / logN

When N is a large number such as N=333

Constant, loglogN, logN, logn^2, NlogN, (1/3)^N, N^(1/2), N, (3/2)^N, N / logN

A guess with out plugging in numbers for N

Constant, loglogn, logn, logn^2, n^(1/2), n, nlogn, (1/3)^n, (2/3)^n, n/logn

This is how I came to my guess, I tried plugging in numbers into N for each fucntion and look at their results. However I got different results of growth order when I used different numbers. I used 2 and 333 for N. Some fucntions grew much faster with a bigger N than with a smaller. I am not sure how to figure out my problem.

Thanks for your help!
• Oct 4th 2006, 07:56 PM
ThePerfectHacker
Quote:

Originally Posted by hotmail590

Constant, logN, logn^2, N, NlogN, N^2, N^3 and 2^N (right side growing the fastest)

I am not sure what your question is.
Below I have attached a hand drawn graph showing each one except the function 2^n because it starts out slow but then overtakes all of them since I was zoomed in I did not want things to get messy. Yes that order is correct.

(Just curious are you doing algorithm complexity in discrete math class?)
• Oct 4th 2006, 08:15 PM
hotmail590
Sorry for the unclarity in my question. To put it simplily, I would like to know if the ordering of the follow fuctions based on growth rate is correct. I tried using this online function grapher and I'm not sure if my results are correct Function Grapher Online

here is what I got (had to kinda pasted 2 graphs together since the program only allows up to 5 functions)

http://www.geocities.com/shini590/graph.bmp

17
(1/3)^n
(3/2)^n
loglogn
logn
n^(1/2)
log(n)^2
n/logn
n
nlogn <-- grows fastest

Yes, this question came to me when I was in class today. I am taking a course on algorithm analysis.

Thanks for your help!
• Oct 4th 2006, 08:28 PM
ThePerfectHacker
Quote:

Constant
loglogn
logn
logn^2
n^(1/2)
n
nlogn
Good
Quote:

(1/3)^n
(2/3)^n
Usually exponentials are the fastest but in this case these are reciprocal exponentials. I would say that they the slowest in growth. In fact, they have no growth at all!
Quote:

n/logn <-- this being the fastest in growth
How can it be faster than nlog n?
If n/log n you are dividing by a number larger than unity?

Quote:

I am take a course on algorithm analysis.
Cool
• Oct 4th 2006, 09:24 PM
hotmail590
Sorry I edited my previous post a couple times perhaps you replied while I was editing it. I noticed some of my mistakes and reordered them.

This is my final answer

(1/3)^n
(3/2)^n
17
loglogn
logn
n^(1/2)
log(n)^2
n/logn
n
nlogn <-- grows fastest

please check (does't log(n)^2 grow faster than n^(1/2) ?)

Thank you very much for your help!