2

I am working with the equation

$T(n) = T(n/2) + n^2$, given $T(1) = 0$.

I started by using backwards substitution arriving at

$T( ( ( n - 1 ) / 2 ) + ( n - 1 ) ^ 2 ) + n ^ 2$ and eventually arrived at

$T( ( n - k ) / 2 )$ + the summation of $(n-i)^2$ from $i = 0...k$. However, I am not sure where to go from here because using $T(1) = 0$ would give $0/2$ plus the summation which gives $0$.

This does not seem like it would work for $n = 1$.

Any suggestions?

Will Byrne
  • 476
CS-DS-ES-FS
  • 31
  • Hint: assume you can write $n = 2^k$ for some $k \in \mathbb{N}$. Then $T(n) = T(2^{k-1}) + n^2$.Then you'll eventually get $T(1)$ at the end and a sum of terms of the form $(n-i)^2$, which should be easy. – K.A. Feb 07 '16 at 02:05
  • For later use, the general case is covered here: https://en.wikipedia.org/wiki/Master_theorem – AHusain Feb 07 '16 at 02:06

2 Answers2

1

Use the substitution $n = 2^k$, $t(k) = T(2^k)$:

$\begin{align} t(k) = t(k - 1) + 2^{2 k} \end{align}$

This linear recurrence is easy to solve (or just write it as $t(k) - t(k - 1) = 2^{2 k}$ and sum over $k$).

vonbrand
  • 27,812
  • 1
    How about the n which are not powers of 2? – marty cohen Feb 07 '16 at 04:27
  • This was my doubt too. My CS teacher does not address this point but it bothers me how a relation on natural numbers is generalised to irrational numbers like log n. – Saikat Feb 07 '16 at 04:47
  • The above gives values for powers of 2. As written, the recurrence makes no sense otherwise. If you really mean $T(\lfloor n / 2 \rfloor)$, you see that the value obtained the way described gives a bound on the solution. – vonbrand Feb 07 '16 at 12:08
1

Let n=$2^k$ for some k. Then we have $$T(2^k)=T(2^{k-1})+2^{2k}$$ $$\Rightarrow T(2^k)=T(2^{k-2})+2^{2(k-1)}+2^{2k}$$ $$\Rightarrow T(2^k)=T(2^{k-3})+2^{2(k-2)}+2^{2(k-1)}+2^{2k}$$ and so on till we get $$T(2^k)=T(2^0)+2^{2(k-(k-1))}+...+2^{2(k-2)}+2^{2(k-1)}+2^{2k}$$ $$\Rightarrow T(2^k)=\sum_{i=0}^{k-1} 2^{2(k-i)}$$ $$\Rightarrow T(2^k)=4\cdot\frac{4^{k}-1}{3}$$

Substituting the value of $2^k=n$ we get $$T(n)=\frac 43\cdot (n^2-1)$$

GTX OC
  • 1,569
  • 2
  • 12
  • 19