1
$\begingroup$

The exercise says "Show that the solution of $T(n) = T(\lceil{n/2}\rceil) + 1$ is $O(\lg(n))$." I came up with a solution for this exercise using the substitution method but I don't know if it is correct. My solution goes like this: I claim $T(n) \leq c\lg{n}$ and assume it holds for $\lceil{n/2}\rceil$, then $$ \begin{aligned} T(n) &\le c\lg(\lceil{n/2}\rceil) + 1 && \text{Inductive Hypothesis}\\ &= c\lg(n/2) + 1 && \text{Omitting ceiling}\\ &= c\lg{n} - c + 1 && \text{Algebra}\\ &\le c\lg{n} && \text{for $c\ge1$} \end{aligned} $$

I omit the ceiling function according to the text.

I, however, found another solution on the internet that is slightly more complicated which makes me think my solution is probably wrong. It states that $T(n) \leq c\lg(n - b)$ and assumes it holds for $\lceil{n/2}\rceil$, consequently:

$$ \begin{aligned} T(n) &\le c\lg({\lceil{n/2-b}\rceil}) + 1 \\ &\lt c\lg(n/2-b + 1) + 1\\ &= c\lg\big(\frac{n-2b+2}{2}\big) + 1\\ &= c\lg(n-2b+2) - c\lg2 + 1\\ &\le c\lg(n - b) \end{aligned} $$ Where the last inequality requires that $b \ge 2$ and $c \ge 1$.

My question is if my solution is correct, then why subtract $b$ from $n$ in the second solution? If my solution is not correct, is subtracting $b$ from $n$ absolutely necessary and why is my solution not correct?

$\endgroup$
4
  • $\begingroup$ In the second line of your solution, you wrote and equality, while the right-hand side is actually smaller than the left. Since the first line is a $\leq$, that replacement in the second line could be a value that it does no longer satisfy the same inequality. $\endgroup$
    – plop
    Nov 10 '20 at 0:49
  • $\begingroup$ The subtraction of $b$ is needed in that second proof, but it is not necessary for a proof. You can adapt the argument to not have any $b$ subtracting, but the you might need to choose larger $c$ and the inequality wont be true for all $n$ but for $n$ sufficiently large. This is, however, OK for the definition of big $O$. $\endgroup$
    – plop
    Nov 10 '20 at 0:56
  • $\begingroup$ It makes sense, I'm guessing I misunderstood when the text said they omitted floors, ceilings and boundary conditions. Would it be then that I cannot omit them amidst a proof, but I should omit them, and only in some cases, before starting such a proof? $\endgroup$
    – Pobs97
    Nov 10 '20 at 4:40
  • $\begingroup$ You can omit the ceiling, that is what they do, but note that there is a $+1$ added inside the logarithm after the ceiling gets removed. That $+1$ is missing in your argument, in the analogous step. $\endgroup$
    – plop
    Nov 10 '20 at 16:39
1
$\begingroup$

As pointed out in the comments, your proof is wrong since it is not true in general that $\log \lceil n/2 \rceil \leq \log n/2$. For example, if $n = 1$ then the left-hand side is zero while the right-hand side is negative.


In the comment you mention that the text states that they omit floors and ceilings. This is always wrong. You cannot "omit" stuff. It invalidates your entire reasoning. (Sometimes, however, you can use true inequalities to get rid of floors or ceilings: for example, $\lfloor x \rfloor \leq x$.)

Consider for example a divide-and-conquer algorithm which splits its input into two halves and performs some $O(n)$ processing. You often see its running time expressed as the recurrence $$ T(n) = 2T(n/2) + O(n). $$ This is clearly wrong – what if $n$ is odd? What does $T(13.5)$ even mean? The argument has to be a positive integer! The real recurrence is probably more like $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n). $$

When the text states that they omit floors and ceilings, they are being sloppy. They allow themselves to do that since you can solve the true recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ via the fake one $T(n) = 2T(n/2) + O(n)$, which should be interpreted as defining a function $T(n)$ for all positive values of $n$.

You can see this sentiment expressed formally in the Akra–Bazzi theorem, where floors and ceilings don't change the answer. Another way to see it is to consider only values of $n$ of the form $n = 2^m$. For these values, the recurrence $T(n) = 2T(n/2) + O(n)$ does hold. You can prove by induction that the solution to the recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$, and so it suffices (in this case) to determine the asymptotic rate of growth for $n$ of the form $n = 2^m$.


How do you solve your recurrence, $T(n) = T(\lceil n/2 \rceil) + 1$? First of all, you have to supply some base case, say $T(1) = C$. Given $n$, we now construct the following sequence: $n_0 = n$, $n_{i+1} = \lceil n_i/2 \rceil$. You can check that $T(n)$ equals $C$ plus the minimal index $i$ such that $n_i = 1$.

Since $\lceil m/2 \rceil \leq (m+1)/2$, we know that $n_1 \leq (n+1)/2$, and so $n_2 \leq (n+3)/4$, and $n_3 \leq (n+7)/8$, and so on. More generally, $n_i \leq (n+2^i-1)/2^i < n/2^i + 1$. Hence if $i = \lceil \log_2 n \rceil$ then $n_i < n/n + 1 = 2$, implying that $n_i \leq 1$.

In the other direction, clearly $n_i \geq n/2^i$, and so if $i = \lceil \log_2 n \rceil - 1 < \log_2 n$ then $n_i > 1$, implying that $T(n) > \lceil \log_2 n \rceil - 1 + C$.

We conclude that the minimal $i$ such that $n_i = 1$ is exactly $\lceil \log_2 n \rceil$. Hence $T(n) = C + \lceil \log_2 n \rceil$.

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