## Logarithmically growing function with finite limit at infini

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### Logarithmically growing function with finite limit at infini

Is it possible to define a function that has the properties that:

f(0) = f0
f(+infinity) = 1

Where 0 <= f0 < 1 and over the region from 0 <= x <= infinity, the function f(x) grows logarithmically.

Any ideas?
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.

gfauxpas
Posts: 97
Joined: Sun Oct 09, 2011 11:24 pm UTC
Contact:

### Re: Logarithmically growing function with finite limit at in

What do you mean by f(+∞)? Do you mean f(x) as x→+ ∞?

And by f(0)=0, do you mean f(1) = 0?

If by "grows logarithmically" you mean "of the form [imath]f:ℝ _{>0} \to ℝ, x \mapsto \lambda \log_a x[/imath] where λ is some non-zero constant and a is some positive constant, then no, because [imath]\log_a x = \dfrac {\ln x}{\ln a}[/imath] and ln x diverges.

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

### Re: Logarithmically growing function with finite limit at in

I'm thinking something along the lines of log(ax)-H_x

gfauxpas
Posts: 97
Joined: Sun Oct 09, 2011 11:24 pm UTC
Contact:

### Re: Logarithmically growing function with finite limit at in

Timefly wrote:I'm thinking something along the lines of log(ax)-H_x

where x is a positive integer? Hx is the harmonic series as a function of x, right?

But I don't know if the OP would call that logarithmic growth. Because look, I can do this: g(x) = ln(ax) - ln x. This clearly converges to ln a...

Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Logarithmically growing function with finite limit at in

Sagekilla wrote:Is it possible to define a function that has the properties that:

f(0) = f0
f(+infinity) = 1

Where 0 <= f0 < 1 and over the region from 0 <= x <= infinity, the function f(x) grows logarithmically.

Any ideas?

You might be interested in logistic growth.
wee free kings

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

### Re: Logarithmically growing function with finite limit at in

gfauxpas wrote:where x is a positive integer? Hx is the harmonic series as a function of x, right?

Eeyup.

gfauxpas wrote:But I don't know if the OP would call that logarithmic growth. Because look, I can do this: g(x) = ln(ax) - ln x. This clearly converges to ln a...

I suppose. I'm not really convinced such a function exists. Would the function I posited be O(ln(x))?

Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Logarithmically growing function with finite limit at in

gfauxpas wrote:Because look, I can do this: g(x) = ln(ax) - ln x. This clearly converges to ln a...

Faster than you might think.

Spoiler:
ln(ax) - ln(x) = ln(a) + ln(x) - ln(x) = ln(a) is constant.

phlip
Restorer of Worlds
Posts: 7551
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Logarithmically growing function with finite limit at in

Timefly wrote:Would the function I posited be O(ln(x))?

Every function that fits the conditions in the OP (or, more generally, every function such that limx -> infty f(x) is a finite value) is in Θ(1), and therefore is (loosely) O(ln(x)).

Yours, in particular, is (with a little twerking) related to the [url=http://en.wikipedia.org/wiki/Euler–Mascheroni_constant]Euler-Mascheroni constant[/url].

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

gfauxpas
Posts: 97
Joined: Sun Oct 09, 2011 11:24 pm UTC
Contact:

### Re: Logarithmically growing function with finite limit at in

Proginoskes wrote:
gfauxpas wrote:Because look, I can do this: g(x) = ln(ax) - ln x. This clearly converges to ln a...

Faster than you might think.

Spoiler:
ln(ax) - ln(x) = ln(a) + ln(x) - ln(x) = ln(a) is constant.

right, which is why I'm not sure the OP would consider such a function "logarithmically growing"

Meem1029
Posts: 379
Joined: Wed Jul 21, 2010 1:11 am UTC

### Re: Logarithmically growing function with finite limit at in

As has been stated, if it grows logarithmically it will approach infinity as x approaches infinity. Something that may fit what you want is 1-a*(1/2)^x, where a=1-f0. At x=0, this is 1-(1-f0)(1)=f0. At infinity, 1/2^x =0, so this equals 1. Note that you can replace 1/2 with any given number between 0 and 1 to adjust the rate it grows at.
cjmcjmcjmcjm wrote:If it can't be done in an 80x24 terminal, it's not worth doing

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### Re: Logarithmically growing function with finite limit at in

Meem1029 wrote:As has been stated, if it grows logarithmically it will approach infinity as x approaches infinity. Something that may fit what you want is 1-a*(1/2)^x, where a=1-f0. At x=0, this is 1-(1-f0)(1)=f0. At infinity, 1/2^x =0, so this equals 1. Note that you can replace 1/2 with any given number between 0 and 1 to adjust the rate it grows at.

That actually works perfectly. If I take f(x) = 1 - (1 - f_0) * k^log(log(x)), with k being in [0, 1) then it has all the properties I need.
The input size that it becomes "large" becomes exponentially huge, and it has a finite limit at x = 0 and x = +infinity.

I have to find the paper I was reading -- this was in relation to time complexity of a particular algorithm. It required certain portions
of the algorithm to take a percentage of total time that grew logarithmically (but that was ultimately negligible for any realistic input size)
with input size. I was curious if there was such a function to model that sort of growth, and the above kind of has the behavior I was