0 votes 0 votes Iterative functions: f(n)= n/logn c=2 What is f*(n) ? How to solve this question? Algorithms algorithms asymptotic-notation + – mb14 asked Jul 6, 2022 mb14 275 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply ankitgupta.1729 commented Jul 7, 2022 reply Follow Share 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$ 0 votes 0 votes mb14 commented Jul 8, 2022 i edited by mb14 Jul 8, 2022 reply Follow Share 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 0 votes 0 votes mb14 commented Jul 8, 2022 reply Follow Share c is used for terminating the function. 0 votes 0 votes ankitgupta.1729 commented Jul 8, 2022 reply Follow Share Thanks. Got your question. Please allow some time. Unable to do now. 1 votes 1 votes Please log in or register to add a comment.