Fonction smaller than iterated logs, but not constant

  • Thread starter fortin946
  • Start date
  • Tags
    Constant
In summary: This is because as logk(x) tends to 0 when k tends to infinity, any function that is eventually smaller than it must also tend to 0, contradicting the requirement of f(x) tending to infinity as x tends to infinity. Therefore, it is not possible to find such a function.
  • #1
fortin946
3
0
I am looking for a continuous and increasing function f(x) which tends to infinity as x tends to infinity.
This function must have the property that it is eventually smaller than logk(x)
(the k-th iterated logarithm) for all k>=1

I have no hint how to find such a function!
One of my problems is that logk(x) tends to 0 when k tends to infinity...
then how is it possible ton find f(x) increasing?!
 
Physics news on Phys.org
  • #2
My thoughts:

Suppose we have found an increasing function h(x) on the interval (0,x_k] such that h(x) is less than than the k th iterated log function log[k](x). Can we extend the definition of h(x) to a larger interval?

There should be some point x_(k+1) > x_k so that log[k+1] (x_(k+1)) = log[k] (x_k) + 1.0
(Eventually log[k+1] (x) must climb up well past the height where log[k] is now.)

You could extend the definition of h(x) by making it a line from h(x_k) to log[k+1](x_(k+1)).

Starting with k = 1, after N steps, you would have defined a function h(x) that is less than log[1+N] (x) on the interval from x_(1+N) to infinity.

To make the above idea precise you have to worry about a lot of details. For example, does repeating the above process extend the domain of definition to arbitrarily large values of x instead of reaching some sort of limit on the x-axis.
 
  • #3
Thanks for the idea! Do we call this function log*(x) ?
 
  • #4
you can always think of an step function that is increasing but piecewise constant and that grows slower than the logarithm and iterated logarithm
 
  • #5
Did you want a function f such that f at some point is smaller than log^k for each k (for which log^k(x) makes sense anyway)? This is different from being smaller than f being less than log^k at some point for each k at some point (the point depending on k that is). There are no function satisfying the first condition, but the latter is already dealt with here.
 
  • #6
fortin946 said:
One of my problems is that logk(x) tends to 0 when k tends to infinity...

No, it doesn't
 

1. What is a function smaller than iterated logs, but not constant?

A function smaller than iterated logs is a function that grows slower than the iterated log function, but still has a non-constant rate of growth. It falls in between constant functions and functions that grow faster than iterated logs.

2. How is a function smaller than iterated logs different from a constant function?

A constant function has a fixed output regardless of the input, while a function smaller than iterated logs has a variable rate of growth. This means that as the input increases, the output will also increase, but at a slower rate.

3. Can you give an example of a function smaller than iterated logs, but not constant?

One example of a function smaller than iterated logs is the Ackermann function. It grows faster than any polynomial function, but still slower than the iterated log function.

4. How is a function smaller than iterated logs related to big O notation?

Big O notation is used to describe the order of growth of a function. A function smaller than iterated logs has a lower order of growth than the iterated log function, and would be represented as O(log log n).

5. Are there any practical applications of functions smaller than iterated logs?

Functions smaller than iterated logs are often used in theoretical computer science to analyze the time complexity of algorithms. They can also be used to model certain natural phenomena, such as the growth of certain types of trees or the spread of diseases.

Similar threads

Replies
2
Views
80
  • Calculus
Replies
5
Views
839
  • Introductory Physics Homework Help
Replies
17
Views
238
Replies
1
Views
833
  • Calculus and Beyond Homework Help
Replies
2
Views
465
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Introductory Physics Homework Help
Replies
2
Views
2K
Replies
4
Views
287
Back
Top