0

I'm trying to find the asymptotic upper and lower bound for $$T(n)=\begin{cases}0& n<2\\ T(n-2)+\log(n) &n\geq2\end{cases}$$

it follows that $T(n-2)=T(n-4)+\log(n-2)$, and therefore for $n\geq 2$

$$T(n)=\begin{cases}T(0)+\sum_{k}^{n/2}\log{(2k)}&\text{if $n$ even}\\ T(1)+\sum_{k}^{(n-1)/2}\log{(2k)}&\text{if $n$ odd} \end{cases}$$

Either way, since evaluating $\log(2k)$ takes $O(1)$ time, and we have to evaluate it $n/2$ or $(n-1)/2$ times, should the upper bound for $T(n)$ then be $O(n/2)=O(n)$?

Even if this is correct, it still feels a bit hand-wavy. Formally we define the big $O$ notation by

$$0 \leq f (n) \leq c \cdot g(n), \text{for all } n \geq n_0$$ for constants $c > 0$ and $n_0 \geq 0$

and similarly $\Omega$ (lower to be where there exits constants $c' > 0$ and $n_1 \geq 0$ such that $$0 \leq c' \cdot g'(n) \leq f (n), \text{for all } n \geq n_1$$

How could we go about finding $g(n)$ and $c$ for $O$ case, $c'$ and $g'(n)$ for $\Omega$ case?

jeb2
  • 645
  • 4
  • 15

1 Answers1

2

The goal here is to get an asymptotic bound on the value of $T(n)$, not the number of operations needed to compute $T(n)$.

Write $n = 2k + r$, where $r \in \{0,1\}$. So we have that:

$$\sum_{i=1}^{k} \log(2i) \leq T(n) \leq \sum_{i=1}^{k+1} \log(2i).$$

Now: $$\int_{2}^{k} \log(2x) \, dx \leq \sum_{i=1}^{k} \log(2i)$$

and $$\sum_{i=1}^{k+1} \log(2i) \leq \int_{1}^{k+2} \log(2x) \, dx.$$

Evaluate the integrals. Now as $n = 2k + r$, we have that $k \in \Theta(n)$. I will let you finish from here.

ml0105
  • 14,674