Time complexity of algorithm inversely proportional to size of sub problem?

Question

Let's say I have an algorithm with time complexity $T_n = T_\frac{n-1}2 + 1$, $T_0 = 0, T_1 = 1$.

Assume (Induction hypothesis) $T_n = C\log_2(n+1)$ for some $C$. $T_1$ imposes $C \geq 1$.

Therefore from I.H. (plugging in the formula at $\frac{n-1}2$):

$$T_n = C\log_2(\frac{n-1}{2}+1) + 1$$ $$T_n = C\log_2(\frac{n+1}{2}) + 1$$ $$T_n = C\log_2(n+1) - C + 1$$ Setting $C = 1$ gives

$$T_n = C\log_2(n+1)$$

And so by induction

$$T_n = \log_2(n+1)$$

This result makes very little sense to me. How come reducing the size of the subproblem from $n/2$ to $(n-1)/2$ increases the time it takes? (From Master's theorem, $T_n = T_{n/2} + 1 \Rightarrow T_n = \log_2(n)$. Similarly, increasing to $(n+1)/2$ gives $T_n = \log_2(n-1)$. What am I failing to see here?

Answer 1

I am afraid that you fell prey to ambiguous notations.

To clarify, the subscript $\frac{n-1}2$ in the recurrence relation, $T_n = T_\frac{n-1}2 + 1$ must mean the integer division of $n-1$ by 2 as used in most programming languages, i.e., $\frac 22=1$ and $\frac32=1$. The following equality does NOT hold,

$$\log_2(\frac{n+1}{2}) = \log_2(n+1) - 1,$$ where the division on the left hand side is the integer division. For example, you can check the case when $n=2$. In the light of that clarification, $T_n = C\log_2(n+1)$ with any constant $C$ cannot be a solution to that recurrence relation.

Now, you might insist that $\frac{n-1}2$ means the usual math division of $n-1$ by 2, i.e., $\frac{3-1}2=1$ and $\frac{4-1}2=1.5$, so that $T_n = C\log_2(n+1)$ could be a solution to that recurrence relation. Well, in that case, that recurrence relation, together with the initial conditions $T_0 = 0$ and $T_1 = 1$ does not define the value of $T_2$, since $T_2=T_{0.5}+1$, where $T_{0.5}$ is not defined. That means, it does not make any sense to involve $T_2$, $T_4$, etc in any equality, since they are not defined!

By the way, it is wrong that "from Master's theorem, $T_n = T_{n/2} + 1 \Rightarrow T_n = \log_2(n)$". What Master's theorem tells us is, $T_n = T_{n/2} + 1 \Rightarrow T_n = \Theta(\log_2(n)).$