# Solving a recurrence relation with floor function

I'm having trouble solving this recurrence relation: \begin{align} T(n) &= \begin{cases} 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} &\text{if } n > 7 \\ 1 &\text{otherwise} \end{cases} \end{align} where $$n \in \mathbb{N}$$. I would prefer to find the explicit solution for $$T(n)$$, but just an asymptotic bound on the solution would be enough.

I guess this is going to be done via substitution method and through induction, but I have no idea how to set it up/solve it. I assume the master theorem cannot be used here, because of the floor function.

I found two similar questions, here and here, but I don't know how their solutions can be adapted to my question.

• I guess there is a typo because, for instance, if $n = 7$ then $\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor = 4$ and hence $T(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5) = T(-1)$, which is not defined. I guess the recurrence relation is defined for $n > 7$, while $T(n) = 1$ for all $0 \leq n \leq 7$. – Taroccoesbrocco Sep 26 '18 at 14:06
• @Taroccoesbrocco: Yes, you are right. Indeed, since $n \in \mathbb{N}$, one has $\big \lfloor \frac{n}{\sqrt{2} } \big\rfloor \geq 5$ if and only if $n > 7$. – Ruggiero Rilievi Sep 27 '18 at 10:00
• So, in the definition of $T(n)$ I replaced the side condition $n > 1$ with $n > 7$. – Taroccoesbrocco Sep 27 '18 at 10:22

Actually, after some manipulations, you can use the master theorem! Let us see how. First, let us prove the following lemma:

Lemma: The function $$T$$ is non-decreasing, i.e. $$T(n) \leq T(n+1)$$ for all $$n \in \mathbb{N}$$.

Proof. By strong induction on $$n \in \mathbb{N}$$.

Base cases: For all $$0 \leq n \leq 6$$, one has $$T(n) = 1 = T(n+1)$$. Moreover, $$T(7) = 1 < 2\,T(0) + 8^{\pi/2} = T(8)$$, as $$\big\lfloor \frac{8}{\sqrt{2}} \big\rfloor =5$$.

Inductive step: Let $$n > 7$$. The strong induction hypothesis is $$T(k) \leq T(k+1)$$ for all $$0 \leq k < n$$. The goal is to prove that $$T(n) \leq T(n+1)$$. By definition, \begin{align} T(n) &= 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} & T(n+1) &= 2\,T\big(\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2}\,. \end{align}

According to the properties of the floor function, $$\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + \big\lfloor \frac{1}{\sqrt{2}} \big\rfloor + 1 = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + 1$$, and $$\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + \big\lfloor \frac{1}{\sqrt{2}} \big\rfloor \leq \big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor$$, since $$\sqrt{2} > 1$$. Therefore, there are only two cases:

• either $$\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor$$ and then $$T(n) \leq 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2} = T(n+1)$$, where the inequality holds because from $$\frac{\pi}{2} > 0$$ it follows that $$n^\frac{\pi}{2} < (n+1)^\frac{\pi}{2}$$ ;
• or $$\big\lfloor \frac{n+1}{\sqrt{2}} \big\rfloor = \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor + 1$$; we can apply the strong induction hypothesis to $$T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 \big)$$ because $$\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5 < n$$ (indeed, $$n + 5 > n = \lfloor n \rfloor \geq \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor$$ since $$\lfloor \cdot \rfloor$$ is non-decreasing), so $$T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 \big)\leq T \big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor- 5 + 1\big) = T \big(\big\lfloor \frac{n + 1}{\sqrt{2}} \big\rfloor- 5 \big)$$ and hence $$T(n) \leq 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + (n+1)^\frac{\pi}{2} = T(n+1)$$. $$\qquad\square$$

As $$T$$ is non-decreasing by the lemma above (and $$\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5 < \big\lfloor \frac{n}{\sqrt{2}} \big\rfloor \leq \frac{n}{\sqrt{2}}$$), for $$n > 7$$ one has $$T(n) = 2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} \leq 2\,T\big(\frac{n}{\sqrt{2}}\big) + n^\frac{\pi}{2}$$. Therefore, if we set \begin{align} S(n) = \begin{cases} 1 &\text{if } n = 0 \\ 2\,S\big(\frac{n}{\sqrt{2}}\big) + n^\frac{\pi}{2} & \text{otherwise} \end{cases} \end{align} then $$T(n) \leq S(n)$$ for all $$n \in \mathbb{N}$$ and so, for any function $$g$$, $$S(n) \in O(g(n))$$ implies $$T(n) \in O(g(n))$$, i.e. the fact that $$S$$ grows asymptotically no faster than $$g$$ implies that $$T$$ grows asymptotically no faster than $$g$$. The point is that we can use the master theorem to find a $$g$$ such that $$S(n) \in O(g(n))$$. Using the same notations as in Wikipedia article: \begin{align} a &= 2 & b&= \sqrt{2} & c_\text{crit} &= \log_\sqrt{2} 2 = 2 & f(n) &= n^{\pi/2} \end{align} thus, $$S(n) \in O(n^2)$$ by the master theorem (since $$\pi/2 < 2 = c_\text{crit}$$), and hence $$T(n) \in O(n^2)$$.