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

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?

• With the same base case, your second recurrence has the solution $1+\log n = \log (2n)$. – Yuval Filmus Jan 19 '20 at 2:22
• @YuvalFilmus Indeed, but also works with $\log(n)$. How can both be solutions? Oh no I see you are right, it can't be $\log(n)$ otherwise $T_1$ would be 0. – Winter Jan 19 '20 at 3:42
• Still that doesn't explain why the $(n-1)/2$ example gives a longer time than $(n+1)/2$. – Winter Jan 19 '20 at 3:51
• It doesn’t give a longer time. That was my point. – Yuval Filmus Jan 19 '20 at 8:10

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

• Once all notations are understood correctly and the correct solutions are given, it will not be true that reducing the size of the subproblem from $n/2$ to $(n-1)/2$ increases the time it takes. – John L. Jan 19 '20 at 14:32
• I think you meant to check the case of the equality when $n = 2$ right? When $n = 1$, $\log_2\frac22 = 0 = \log_22 - 1$. I do get your point about that though. – Winter Jan 19 '20 at 15:48
• Thank you! I'll go back over all my proofs fixing the points you mentionned. – Winter Jan 19 '20 at 15:50