483 views
1 votes
1 votes

For a given constant c $\in \mathbb{R}$, we define the iterated function $f_{c}^{*}$ by

$f_{c}^{*}$(n)=min{${i\geq 0: f^{(i)}(n)<c}$}

For each of the following function f(n) and constants c, give as tight a bound as possible on $f_{c}^{*}$

f(n) c $f_{c}^{*}$(n)
$\sqrt{n}$ 2  
$\sqrt{n}$ 1  
n/lg n 2  

1 Answer

0 votes
0 votes
$f_{c}^*$ means how many times taking  function so it will become $'c'$

for f(n)=$\sqrt{n}$ ,c=2 $\rightarrow$ how many times taking root so it become 2

$n^{\frac{1}{2}}$  $\rightarrow$ $n^{\frac{1}{2^2}}$ $\rightarrow$  $n^{\frac{1}{2^3}}$....... $n^{\frac{1}{2^k}}$

$n^{\frac{1}{2^k}}$=2

k=$log \ logn$.    $f_{c}^*$=$log \ logn$

2.f(n)=$\sqrt{n}$ ,c=2 it can not be converge .($n^{\frac{1}{2^k}}$=1)
Answer:

Related questions

0 votes
0 votes
0 answers
1
Swapnil Naik asked Jul 23, 2018
635 views
I didn't understand Big-O notation: This is CORMEN exercise problem - 3.1-2Solution link: https://www.csee.umbc.edu/~nam1/TA/HWSols/hw1sol.pdf
0 votes
0 votes
1 answer
3
Shyam Singh 1 asked May 17, 2016
822 views
$6.2-3$What is the effect of calling MAX-HEAPIFY(A,i) when the element A[i] is larger that its children?
0 votes
0 votes
0 answers
4