0
$\begingroup$

I realise there's plenty of similar questions all over the site, but I'm yet to find one with either a fraction, or T(1) being equal to an algebraic constant.

The recurrence in question is: $$T(n) = a, n = 1$$ $$T(n) = c + T (\frac{n}{2}), n > 1$$

I am asked to prove by induction that $T(n) ∈ O(log n)$.

I believe the first step is to try and find an explicit formula involving n for the recurrence, and this formula is then used for the base case. It was suggested to use a ceiling function for $T(\frac{n}{2})$ since non-integers are undefined.

This leads to the first 9 cases being: $$T(1) = a$$ $$T(2) = c+a$$ $$T(3) = 2c+a$$ $$T(4) = 2c+a$$ $$T(5) = 3c+a$$ $$T(6) = 3c+a$$ $$T(7) = 3c+a$$ $$T(8) = 3c+a$$ $$T(9) = 4c+a$$

From here I should be able to find a formula, but it eludes me.

Once the formula is found I should then take the typical induction steps, but obviously I am yet to even get that far.

$\endgroup$
1
$\begingroup$

From

$$T(n)=c+T\left(\frac n2\right),$$ we deduce $$T(n)=2c+T\left(\frac n4\right),$$

$$\cdots$$

$$T(n)=ck+T\left(\frac n{2^k}\right).$$

When $k$ is such that $n/2^k=1$,

$$T(n)=ck+a.$$

Obviously this occurs with

$$k=\lfloor\log_2n\rfloor.$$

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