2
$\begingroup$

Recently I proved a some bound about something. The bound is (details : come soon)

Upper bound $f(k)< k^{k^{O(k)}}$.

Lower bound $f(k)< k^{k^2-o(k)}$


My question is

  1. Are these two bounds close? For general meaning.

  2. What should I call the lower bound? An exponential function? Or something other looks like a litter larger. Clearly it is not as large as double exponential.

  3. Should I need to stress that the exponent in the lower bound is $k^2$.

1 Answers 1

1

For large, and even medium-sized $k$, the upper bound is hugely bigger than the lower bound. But for $k$ not too large, the two bounds might be not far from each other if the implied constant in the $O(k)$ is very close to $0$.

The $O(k)$ means that for the upper bound, all we know is that the exponent of $k$ is, for large $k$, less than $k^{ck}$ for some constant $c$. The lower bound is not quite put in lower bound language: a lower bound means a floor below which a function does not go, so I assume that what is meant is $f(k)\gt k^{k^2-o(k)}$. Thus the exponent of $k$ is of size roughly $k^2$.

So already for the upper bound, the exponent of $k$ is a fast growing function, while the exponent in the lower bound grows relatively slowly.

In each case, exponentiating results in very fast growing functions. However, the upper bound grows enormously faster.

  • 0
    Thanks very much for the answer。I really need the “for large” answer。2012-12-21