How to solve the recurrence $T(n) = T\left(\lceil\frac{n}{\sqrt{2}}\rceil+1\right) + 1$?

How to solve the recurrence $T(n) = T\left(\lceil\frac{n}{\sqrt{2}}\rceil+1\right) + 1,\ T(n) = 1$ for $n \leq 8$?

Ignoring the ceil and using the Master Theorem I have $$a = 1,\ b = \sqrt{2},\ log_b(a) = log_\sqrt{2}(1) = 0,\ w(n) = 1$$ So we are in case 2: $$w(n) = \Theta(n^{log_b(a)})$$ and then $$T(n) = \Theta\left(log(n)\right)$$ I know from Wolfram Alpha that exists a more precise estimation $$T(n) \approx 2\cdot log_2(n)$$ How can I achieve this?

Solution 1:

An attempt to justify the Wolfram Alpha result.

As

$$ T\left(\gamma^{\log_{\gamma}n}\right)=T\left(\gamma^{\log_{\gamma}\left(\frac{n}{\gamma}\right)}+1\right)+1 $$

now assuming $n \ge N$ and $\gamma^{\log_{\gamma}\left(\frac{N}{\gamma}\right)}>> 1$ making $\mathbb{T}\left(\cdot\right)=T\left(\gamma^{(\cdot)}\right)$ and $z = \log_{\gamma}n$ we follow with

$$ \mathbb{T}\left(z\right)=\mathbb{T}\left(z-1\right)+1 $$

with solution

$$ \mathbb{T}\left(z\right)=z+c_0 $$

and now going backwards with $z = \log_{\gamma}n$ we get at

$$ T(n) \approx \log_{\gamma}n + c_0 $$

and considering $\gamma = \sqrt{2}$

$$ T(n) \approx 2\log_2 n $$