Thread: 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!

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

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!

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

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!