3

How do you solve the recurrence $T(n) = T(⌈n/2⌉) + 1$ is $O(\lg n)$?

In this explanation, I don't understand how the guess is made:

We guess $T(n)\le c \lg(n−2)$:

$$ T(n)\le c \lg(⌈n/2⌉−2)+1 \le c \lg(n/2+1−2)+1 $$ $$ \le c \lg((n−2)/2)+1 \le c \lg(n−2) − c \lg2 + 1 $$ $$ \le c \lg(n−2)$$

hardmath
  • 37,015
Student
  • 141
  • 1
    @hardmath corrected – Student May 04 '15 at 17:48
  • We are told that doubling the argument of $T$ increases the value by not more than $1$, so the initial conjecture that it is $O(\lg n)$ is natural and plausible, right? – hardmath May 04 '15 at 17:57
  • What do you want to know? It looks clear – Salomo May 04 '15 at 17:58
  • @Salomo: The OP is asking how the "induction hypothesis" was arrived at, how it was "guessed". – hardmath May 04 '15 at 17:59
  • I see. We can make guess by listing $T(n)$ from $n=1,2,3,\dots$, and observe how it can be bounded by constant times logarithmic function. Does it help? – Salomo May 04 '15 at 18:03
  • @Salomo but where does the $n-2$ come from? Thanks – Student May 04 '15 at 18:22
  • Sometimes it is hard to explain how to guess in short, perhaps you can try guessing if $+1$ is changed to $+3$, then you may have a better view. – Salomo May 04 '15 at 18:24

3 Answers3

5

Here is the answer in this image

Here is the very clear answer in this image. I'm writing this because this is compulsory otherwise I don't find text is important. So you want this answer check this image.

Parcly Taxel
  • 103,344
Abhijeet Singh Rajput
  • 51
  • 3
    Instead of writing meaningless text because it is "compulsory", it would have been better to reproduce the solution in the image as text. – Null Dec 11 '17 at 15:19
0

It's a bit like how we work out a value $\delta \gt 0$ given $\epsilon \gt 0$ when doing limits. Try something and if it works great; if not see what can be adjusted or restricted to overcome the obstacle.

Just as when doing the epsilon-delta arguments for limits, we know we can always combine restrictions on delta from one part of an estimate with those from another part, when doing the big-Oh arguments we keep in mind that the estimates only need to hold for "sufficiently large $n$".

Since we want $O(\lg n)$, I might first try (naively) an estimate of $T(n) \le \lg(n)$, just to see how the estimate goes. That is, assuming a strong induction argument will be needed, we would check:

$$ T(n) = T(\lceil n/2 \rceil) + 1 \le \lg(\lceil n/2 \rceil) + 1 $$

But then we are a bit stuck as $\lceil n/2 \rceil$ can be slightly more than $n/2$. We need somehow to be able to absorb that extra amount.

This motivates trying a more general form of the estimate, with some extra parameters for flexibility. That might be an estimate:

$$ T(n) \le c \lg(n + k) $$

where I've introduced the factor $c$ and offset (shift) $k$. Clearly a factor $c > 0$ will not hurt the estimate $O(\lg n)$ since a multiplicative factor is "hidden" in the big-Oh notation automatically. The shift $k$ is also not a deal breaker as the estimate is only imposed "for all sufficiently large $n$", and as $n$ grows, $\lg n$ and $\lg(n + k)$ will tend to differ by an arbitrarily small amount compared to $\lg n$. We will be justified in "absorbing" that offset into a larger coefficient, e.g. for all sufficiently large $n$:

$$ \lg(n+k) \le 2 \lg n $$

where the size of "sufficiently large" depends on the value $k$, but this is okay as far as conserving $O(\lg n)$.

hardmath
  • 37,015
0

Assume $n$ to be a power of $2$, and define $R(k)=T(2^k)$.

Then

$$R(k)=R(k-1)+1,$$ $$R(k)=O(k),$$ $$T(n)=O(\log(n))$$ gives the general behavior.

You can refine to establish

$$T(n)<c\log(n-b)+a$$ with well-chosen constants.