Writing functions with respect to its growth rate
I have put n= 100 in all the functions to note down the resultant value. Greater the value, greater its growth rate. Please correct me if I am using the right approach to judge the growth rate of function e.g logn, e^n , etc
I'm sorry, but you need to be a little bit more detailed.
What does "put n= 100 in all the functions" mean?
What are you trying to calculate the growth rate of?
How is n incremented or decremented?
What approach are you using that we are to evaluate?
What does "put n= 100 in all the functions" mean?
What are you trying to calculate the growth rate of?
How is n incremented or decremented?
What approach are you using that we are to evaluate?
I have to write functions orderwise with respect to the growth rate. I have seen this definition on internet : The growth rate for an algorithm is the rate at which the cost of the algorithm grows as the size of its input grows.
So for example I have been given functions: log(n), e^n, 2^n etc. I have to arrange them and write them orderwise with highest growth rate function at the end and lowest one in the start.
So putting n =100 in all functions will generate a value. Can I use that value to judge the growth rate?
So for example I have been given functions: log(n), e^n, 2^n etc. I have to arrange them and write them orderwise with highest growth rate function at the end and lowest one in the start.
So putting n =100 in all functions will generate a value. Can I use that value to judge the growth rate?
| So putting n =100 in all functions will generate a value. Can I use that value to judge the growth rate? |
Obviously not. Consider:
f(x): x * 2 g(x): (x - 100) * 1000 (100) == 200 g(100) == 0 But: f(10000) == 20000 g(10000) == 9900000 |
Or consider:
f(x): x**2 g(x): (x**3)/1000000 f(100) = 10000 g(100) = 1 f(1000000) = 1000000000000 g(1000000) = 1000000000000 f(1000000000) = 1000000000000000000 g(1000000000) = 1000000000000000000000 |
What you want to compare is the limit of the ratios of the functions as x grows without bound.
lim as x->inf of (f(x) / g(x)) |
If it approaches infinity, than f grows faster.
If it approaches 0 than g grows faster.
If it approaches a constant, they have the same growth rate.
Last edited on
What if i have been given 10 functions and then I have to arrange them order wise? How to deal with that?
the most common ones are
1
lg(n)
n
n*lg(n)
//unusual, N^(c1/c2) here where c1/c1 > 1
n*n
...higher powers of n
c^N (e, 2, 10, other constants to the nth power)
factorial etc needed (nothing used takes factorial time that I know of, do you need any of the oddball and uncommon ones?)
which are in that order for LARGE N but may flip flop for small n for specific functions due to the (removed in notation but still there) constants. Eg if doing 1 thing takes a nanosecond, and you have two functions, first takes 10 seconds + Nlg(n) its slower than second function that takes 0 seconds + N*N for a while. Eventually the N*N overwhelms the constant and is slower again.
Yes, in my experience, it is OK to print the count of what you are counting and run the algorithm with n = 1, 10, 100, 1000, ... up to some value 'in practice'. The curve will tell you which big-O you have if you do it right -- which means you can recognize the curve correctly AND you tested the function correctly (worst case or average case or whatever you are looking at). Its not presentable in a thesis but it will get you the answer.
1
lg(n)
n
n*lg(n)
//unusual, N^(c1/c2) here where c1/c1 > 1
n*n
...higher powers of n
c^N (e, 2, 10, other constants to the nth power)
factorial etc needed (nothing used takes factorial time that I know of, do you need any of the oddball and uncommon ones?)
which are in that order for LARGE N but may flip flop for small n for specific functions due to the (removed in notation but still there) constants. Eg if doing 1 thing takes a nanosecond, and you have two functions, first takes 10 seconds + Nlg(n) its slower than second function that takes 0 seconds + N*N for a while. Eventually the N*N overwhelms the constant and is slower again.
Yes, in my experience, it is OK to print the count of what you are counting and run the algorithm with n = 1, 10, 100, 1000, ... up to some value 'in practice'. The curve will tell you which big-O you have if you do it right -- which means you can recognize the curve correctly AND you tested the function correctly (worst case or average case or whatever you are looking at). Its not presentable in a thesis but it will get you the answer.
Last edited on
| lost110 wrote: |
|---|
| What if i have been given 10 functions and then I have to arrange them order wise? How to deal with that? |
You do exactly the same as if you had to sort 10 numbers. @dutch has told you how to define <, ==, > comparisons for the asymptotic behaviour of functions.
Substituting a numerical value is not OK. After all,
1000 mm looks "large" from its numerical value
1 m looks "modest" from its numerical value
... but obviously they are the same quantity.
Topic archived. No new replies allowed.