algorithmsrecursive algorithms
I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such algorithm:
$$T(n) = T\left(n-\lceil\sqrt n\rceil\right) + 1$$
I know that: $T(0)=0$, $T(1) = 1$.
I tried substituting $n=2^{2^k}$ but it did not get me far.
As mentioned in comment, the first two conditions $T(1) = 0, T(2) = 1$ is incompatible with the last condition $$\require{cancel} T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) = 2\quad\text{ for } \color{red}{\cancelto{\;\color{black}{n > 2}\;}{\color{grey}{n \ge 2}}} \tag{*1}$$ at $n = 2$. We will assume the condition $(*1)$ is only valid for $n > 2$ instead.
Let $\displaystyle\;f(z) = \sum\limits_{n=2}^\infty T(n) z^n\;$ be the generating function for the sequence $T(n)$. Multiply the $n^{th}$ term of $(*1)$ by $z^n$ and start summing from $n = 3$, we obtain:
$$\begin{array}{rrl} &f(z) - z^2 &= T(3) z^3 + T(4) z^4 + T(5) z^5 + \cdots\\ &&= (T(2) + 2)z^3 + (T(2) + T(2) + 2)z^4 + (T(2)+T(3)+2)z^5 + \cdots\\ &&= (1+z)^2 ( T(2)z^3 + T(3)z^5 + \cdots) + 2(z^3 + z^4 + z^5 + \cdots)\\ &&= \frac{(1+z)^2}{z}f(z^2) + \frac{2z^3}{1-z}\\ \implies & f(z) &= \frac{(1+z)^2}{z}f(z^2) + z^2\left(\frac{1+z}{1-z}\right)\\ \implies & \frac{(1-z)^2}{z} f(z) &= \frac{(1-z^2)^2}{z^2}f(z^2) + z(1-z^2) \end{array} $$ Substitute $z^{2^k}$ for $z$ in last expression and sum over $k$, we obtain
$$f(z) = \frac{z}{(1-z)^2}\sum_{k=0}^\infty \left(z^{2^k} - z^{3\cdot2^k}\right) = \left( \sum_{m=1}^\infty m z^m \right)\sum_{k=0}^\infty \left(z^{2^k} - z^{3\cdot2^k}\right)$$
With this expression, we can read off $T(n)$ as the coefficient of $z^n$ in $f(z)$ and get
$$T(n) = \sum_{k=0}^{\lfloor \log_2 n\rfloor} ( n - 2^k ) - \sum_{k=0}^{\lfloor \log_2(n/3)\rfloor} (n - 3\cdot 2^k)$$
For $n > 2$, we can simplify this as $$\bbox[4pt,border: 1px solid black;]{ T(n) = n \color{red}{\big(\lfloor \log_2 n\rfloor - \lfloor \log_2(n/3)\rfloor\big)} - \color{blue}{\big( 2^{\lfloor \log_2 n\rfloor + 1} - 1 \big)} + 3\color{blue}{\big( 2^{\lfloor \log_2(n/3)\rfloor +1} - 1\big)}}\tag{*2}$$
There are several observations we can make.
When $n = 2^k, k > 1$, we have $$T(n) = n(k - (k-2)) - (2^{k+1} - 1) + 3(2^{k-1} - 1) = \frac32 n - 2$$
When $n = 3\cdot 2^{k-1}, k > 0$, we have $$T(n) = n(k - (k-1)) - (2^{k+1} - 1) + 3(2^k - 1) = \frac53 n - 2$$
For $2^k < n < 3\cdot 2^{k-1}, k > 1$, the coefficient for $n$ in $(*2)$ (i.e the factor in red color) is $2$, while the rest (i.e those in blue color) didn't change with $k$. So $T(n)$ is linear there with slope $2$.
Combine these, we find in general
$$\frac32 n - 2 \le T(n) \le \frac53 n - 2 \quad\text{ for }\quad n > 2$$ and $T(n) = O(n)$ as expected. However, $\frac{T(n)}{n}$ doesn't converge to any number but oscillate "between" $\frac32$ and $\frac53$.
Above is a picture ilustrating the behavior of $T(n)$. The blue pluses are the value of $T(n) - (\frac32 n - 2)$ computed for various $n$. The red line is $\frac{n}{6} = (\frac53 n - 2) - (\frac32 n - 2)$. As one can see, $T(n)$ doesn't converge to any straight line. Instead, it oscillate between lines $\frac32 n - 2$ and $\frac53 n - 2$ as discussed before.
That doesn't seem quite right!
Assume we're at the stage where we have $k$ sorted array, each of size $m$ and we'd like to know how many comparisons are needed to form the final sorted array. Take the first two arrays, each of size $m,$ we need $2m-1$ comparisons to make a sorted array, then take the third and fourth arrays, again with $2m-1$ comparisons and continue to get to the final array. So far, we have done $k/2(2m-1)$ comparisons in total, as there're $k/2$ pairs, like $(1,2), (3,4), \cdots.$ Now, we have, $k/2$ arrays each of size $2m.$ With the same approach, take the first and second one (which the first is the result of the first and second arrays from the previous step), we need $4m-1$ comparisons. Again, continue pairing them up until you get the last array. In this step, we've done $(k/4)(4m-1)$ comparisons. Counting the comparisons of the previous step we have done $k/2(2m-1) + k/4(4m-1)$ comparisons in total, so far. Keep going until you get to the final step, where there is only one sorted array. Now, we have to sum up all comparisons. For simplicity, let $k=2^t,$ so $t=\log k$ Then the total number of comparisons is
$$k/2(2m-1) + k/4(4m-1)+\cdots + k/2^t(2^tm-1)$$
which is
$$\sum_{i=1}^t2^{t-i}(2^im-1)=t2^tm-(2^t-1) = n \log k - k +1$$
where we used $2^0+2^1+\cdots+2^{t-1} = 2^t-1$ and $mk=n.$
Therefore, $T(n)=kT(n/k) + n \log k - k + 1.$
Best Answer
As did has already pointed out, $T(n)\sim2\sqrt{n}$. Any easy way to arrive at this conclusion is to pretend $T(n)$ is defined for all real numbers and continuous, and approximate $$ 1=T(n)-T(n-\lceil\sqrt{n}\rceil)\approx\sqrt{n}T'(n) $$ for large $n$, which makes $T'(n)\approx1/\sqrt{n}$ and in turn, by integration, $T(n)\approx2\sqrt{n}$.
Computing $T(n)$ using Maple, indeed reveals that $$ T(n)=2\sqrt{n}-\frac{\ln(2\sqrt{n}+1)}{\ln2}+\epsilon_n $$ where $\epsilon_n\in[-0.1,1]$.
A more formal proof of $T(n)\sim2\sqrt{n}$ is possible, but a bit more technical.
Let's write $n'=n-\lceil\sqrt{n}\rceil$. Then, $$ \left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{5}{4}\le n-\sqrt{n}-1\le n' \le n-\sqrt{n}=\left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{1}{4}. $$
First, assume $T(k)\le2\sqrt{k}$ for $k<n$: this holds for $k<1$, which starts the induction. Then, using $n'<(\sqrt{n}-1/2)^2$, $$ T(n)=T(n')+1\le2\sqrt{n'}+1\le 2\left(\sqrt{n}-\tfrac{1}{2}\right)+1=2\sqrt{n}. $$
Next, assume $T(n)\ge2\sqrt{n}-\tau(n)$ for some function $\tau(n)$. Using $$ 2\sqrt{n'} \ge \sqrt{(2\sqrt{n}-1)^2-5} \ge 2\sqrt{n}-1-\frac{5}{2\sqrt{n}-1}, $$ this makes $$ T(n)=T(n')+1\ge 2\sqrt{n'}+1-\tau(n') \ge 2\sqrt{n}-\frac{5}{2\sqrt{n}-1}-\tau(n'), $$ and so $T(n)\ge 2\sqrt{n}-\tau(n)$ holds if we define $\tau(0)=0$ and $$ \tau(n)=\tau(n')+\frac{5}{2\sqrt{n}-1}. $$ In turn, we now have $$ \frac{\tau(n)-\tau(n')}{n-n'} =\frac{5}{(2\sqrt{n}-1)\cdot\lceil\sqrt{n}\rceil} \le\frac{5}{(2\sqrt{n}-1)\cdot\sqrt{n}} <\frac{5+\delta}{2n} $$ for any $\delta>0$ and sufficiently large $n$. From this follows that $\tau(n)$ at worst is $O(\ln n)$.