1. ## 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.

2. 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?)

3. 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.

4. Constant
loglogn
logn
logn^2
n^(1/2)
n
nlogn
Good
(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!
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?

I am take a course on algorithm analysis.
Cool

5. 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.

(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!