Iteration Functions (Cormen)

Question

Iterative functions:

f(n)= n/logn

c=2

What is f*(n) ?

How to solve this question?

Comments

Could you please define $f^* (n) ?$ In Cormen, iterated logarithm function is defined. How would you define $f^* (n)$ here ?

Also, what is the role of $c=2$ here ?

As you have mentioned iterative function here, so you can write:

$f(n) = \frac{n}{\log n}$

Now, here defining $f^2(n)$ as $f(f(n))$ i.e. composition of two functions i.e. $f \circ f$ and not defining $f^2 (n) = (f(n))^2$ and so,

$f^2 (n) = f(f(n)) = f(\frac{n}{\log n})  = \frac{n}{\log n \log \frac{n}{\log n}}$

Similarly, $f^3 (n) = f(f^2(n)) = \frac{n}{\log n \log \frac{n}{\log n}\log \frac{n}{\log n \log \frac{n}{\log n}}}  $

 $f^i (n) = \frac{n}{g(n) \log \frac{n}{g(n)}}$ for $i \geq 1$

And if you observe, $f^i (n) = \frac{f^{i-1}}{\log f^{i-1}}$ for $i \geq 1$

---

For a given constant c, we define the iterated function f*(n)= min(i>=0: f^i (n) <=c}

Means f*(n) is the number of iterated applications of the function f required to reduce its argument down to c or less.

I have taken this question from Cormen exercise. You can refer to it for better understanding.

@ankitgupta.1729

---

c is used for terminating the function.

---

Thanks. Got your question. Please allow some time. Unable to do now.