Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

1 Answer 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.

share|improve this answer
    
Thanks very much for the answer。I really need the “for large” answer。 –  Yao Wang Dec 21 '12 at 9:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.