[Math] Solving a recurrence relation with floor function

algorithmsasymptoticscomputational complexityinductionrecurrence-relations

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.

Best Answer

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)$.

Related Question