2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ With the same base case, your second recurrence has the solution $1+\log n = \log (2n)$. $\endgroup$ – Yuval Filmus Jan 19 '20 at 2:22
  • $\begingroup$ @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. $\endgroup$ – Winter Jan 19 '20 at 3:42
  • $\begingroup$ Still that doesn't explain why the $(n-1)/2$ example gives a longer time than $(n+1)/2$. $\endgroup$ – Winter Jan 19 '20 at 3:51
  • 1
    $\begingroup$ It doesn’t give a longer time. That was my point. $\endgroup$ – Yuval Filmus Jan 19 '20 at 8:10
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – John L. Jan 19 '20 at 14:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Winter Jan 19 '20 at 15:48
  • $\begingroup$ Thank you! I'll go back over all my proofs fixing the points you mentionned. $\endgroup$ – Winter Jan 19 '20 at 15:50

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.