-1

My friends and I are having trouble resolving this...

T1 = 1,

T(n) = 2T(n/2) + 1, n > 1.

I would appreciate if anyone could help us solve this, and explain how to.

Wethrin
  • 1
  • What do you mean by $n/2$ if $n$ is odd? – Hans Lundmark Apr 29 '21 at 17:20
  • Hi and welcome to Math.SE. It would be preferable to use MathJax for mathematical expressions. You can get started here, and a more complete reference can be found here. – user3733558 Apr 29 '21 at 17:23
  • @HansLundmark Generally in this kind of "get the complexity of the algorithm" type of problems, we do not care about such details (we consider $T$ defined on the reals, but only interested in values taken at integers), in fact we solve for $n=2^p$ and even take the log after. But I agree it would matter if we were to solve this as a true functional equation for integers only. – zwim Apr 29 '21 at 17:39

2 Answers2

0

Hints:

  • set $T(n)=U(n)-1$ to get rid of the constant term $+1$
  • set $n=2^p$ and $V(p)=U(n)$ to linearize the equation
  • solve for $V$
  • get back the chain of substitutions to express $T$ (use $p=\log_2(n)$ if necessary)
zwim
  • 28,563
0

Considering $n = 2^m$ we have

$$ T\left(2^m\right)=2T\left(2^{m-1}\right)+1 $$

now calling $\mathbb{T}(\cdot)=T\left(2^{(\cdot)}\right)$ we have

$$ \mathbb{T}(m)= 2\mathbb{T}(m-1)+1 $$

this linear recurrence has as soluttion

$$ \mathbb{T}(m)= c_0 2^{m-1}+2^m - 1 $$

or equivalently

$$ T\left(2^m\right)=c_0 2^{m-1}+2^m - 1 $$

then

$$ T(n) = c_0 \frac n2 + n - 1 = c_1 n -1 $$

but $T(1) = c_1-1=1\Rightarrow c_1 = 2$ hence

$$ T(n) = 2n-1 $$

Cesareo
  • 33,252