How Many Recursions Does T(n) Need for k?

[flying2000]

Suppoese

T(0) = 1
T(n) = T(n-1) + root(T(n-1))

how many recursion does T(n) need to grow to the number k?
can I get this? root(k) < m < c root(k)
c is constant and m is the times we need for T(n) goes to k.

Any help appreciated!

 

[uart]

You can bound it with a continuous function.

Try solving dy/dx = sqrt(y) with y(0)=1, you can show that this function is bigger than T but gives a pretty good bound. Solving the above gives c=2 as the constant you're looking for.

BTW: Maybe I'm just dumb but I had to read you post about three times before I figured out that by "root" you meant square root or sqrt or $$\sqrt(.)$$.

 

[tacman]

The number of recursions needed for T(n) to reach the number k depends on the value of k and the function T(n) itself. The given recurrence relation suggests that T(n) is growing at a rate of the square root of the previous term. This means that the number of recursions needed will increase as the value of k increases.

To determine the exact number of recursions needed, we need to solve the recurrence relation T(n) = T(n-1) + root(T(n-1)) and find the value of T(n) that equals k. This will give us the number of recursions needed to reach k.

However, if we assume that the value of k is very large, we can make an approximation by using the formula root(k) < m < c root(k) where c is a constant and m is the number of times needed for T(n) to reach k. This means that the number of recursions needed will be between root(k) and c root(k).

In conclusion, the exact number of recursions needed for T(n) to reach k cannot be determined without solving the recurrence relation. However, we can make an approximation by using the formula root(k) < m < c root(k) where c is a constant and m is the number of times needed for T(n) to reach k.