Skip to main content
formatting
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Is there a topology on growth rates of functions?  

I've often idly wondered one can say about the collection of "growth rates". By growth rate, let's say we mean an equivalence class of functions (0,infty) \to (0,\infty)$(0,\infty) \to (0,\infty)$, where two functions f_1$f_1$,f_2 $f_2$ are equivalent if f_1/f_2$f_1/f_2$ and f_2/f_1$f_2/f_1$ are bounded away from 0$0$ and infinity. You can add, and multiply them, and they form a poset under the pordering where f_1 <= f_2$f_1 \le f_2$ if f_1/f_2$f_1/f_2$ is bounded above.

So, in loose terms, does the sequence xlog(1+x)$x\log(1+x)$, xlog(log(10+x))$x\log(\log(10+x))$, xlog(log(log(100+x)))$x\log(\log(\log(100+x)))$, ... convergeconverges to x$x$ in some natural way? With a little thought you can construct a growth rate which is strictly greater than x$x$ and strictly less than all growth rates in that sequence, so it probably no. Still is there any sort of natural "topology"? Can you find a directed set of growth rates which are linearly ordered, and eventually smaller than anything larger than x$x$?

There's probably a better way to look at this (which is why I ask). =)

Is there a topology on growth rates of functions?  

I've often idly wondered one can say about the collection of "growth rates". By growth rate, let's say we mean an equivalence class of functions (0,infty) \to (0,\infty), where two functions f_1,f_2 are equivalent if f_1/f_2 and f_2/f_1 are bounded away from 0 and infinity. You can add, and multiply them, and they form a poset under the pordering where f_1 <= f_2 if f_1/f_2 is bounded above.

So, in loose terms, does the sequence xlog(1+x), xlog(log(10+x)), xlog(log(log(100+x))), ... converge to x in some natural way? With a little thought you can construct a growth rate which is strictly greater than x and strictly less than all growth rates in that sequence, so it probably no. Still is there any sort of natural "topology"? Can you find a directed set of growth rates which are linearly ordered, and eventually smaller than anything larger than x?

There's probably a better way to look at this (which is why I ask). =)

Is there a topology on growth rates of functions?

I've often idly wondered one can say about the collection of "growth rates". By growth rate, let's say we mean an equivalence class of functions $(0,\infty) \to (0,\infty)$, where two functions $f_1$, $f_2$ are equivalent if $f_1/f_2$ and $f_2/f_1$ are bounded away from $0$ and infinity. You can add, and multiply them, and they form a poset under the pordering where $f_1 \le f_2$ if $f_1/f_2$ is bounded above.

So, in loose terms, does the sequence $x\log(1+x)$, $x\log(\log(10+x))$, $x\log(\log(\log(100+x)))$, ... converges to $x$ in some natural way? With a little thought you can construct a growth rate which is strictly greater than $x$ and strictly less than all growth rates in that sequence, so it probably no. Still is there any sort of natural "topology"? Can you find a directed set of growth rates which are linearly ordered, and eventually smaller than anything larger than $x$?

There's probably a better way to look at this (which is why I ask).

Source Link
Mike Hall
  • 793
  • 6
  • 15

Is there a topology on growth rates of functions?

I've often idly wondered one can say about the collection of "growth rates". By growth rate, let's say we mean an equivalence class of functions (0,infty) \to (0,\infty), where two functions f_1,f_2 are equivalent if f_1/f_2 and f_2/f_1 are bounded away from 0 and infinity. You can add, and multiply them, and they form a poset under the pordering where f_1 <= f_2 if f_1/f_2 is bounded above.

So, in loose terms, does the sequence xlog(1+x), xlog(log(10+x)), xlog(log(log(100+x))), ... converge to x in some natural way? With a little thought you can construct a growth rate which is strictly greater than x and strictly less than all growth rates in that sequence, so it probably no. Still is there any sort of natural "topology"? Can you find a directed set of growth rates which are linearly ordered, and eventually smaller than anything larger than x?

There's probably a better way to look at this (which is why I ask). =)