3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Taroccoesbrocco Sep 26 '18 at 14:06
  • 1
    $\begingroup$ @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$. $\endgroup$ – Ruggiero Rilievi Sep 27 '18 at 10:00
  • 1
    $\begingroup$ So, in the definition of $T(n)$ I replaced the side condition $n > 1$ with $n > 7$. $\endgroup$ – Taroccoesbrocco Sep 27 '18 at 10:22
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.