3

Any hints on how to solve $t(n) = t\left(\frac n2\right) + n^2$ with the iteration method? What I've got so far:

$$t(n)=n^2+t\left(\frac n2\right)$$

$$t(n)=n^2+\left(\frac n2\right)^2+t\left(\frac n4\right)$$

$$t(n)=n^2+\left(\frac n2\right)^2+\left(\frac n4\right)^2+t\left(\frac n8\right)$$

$$t(n)=\sum_{i=0}^{k-1}\frac {n^2}{4^i}+t(1)\text{ with }n=2^k\text{ and }k=\log_2n$$

$$t(n)=n^2\sum_{i=0}^{k-1}\frac 1{4^i}+t(1)$$

abiessu
  • 8,115
Chafic
  • 133
  • 1
    That appears to be very good so far, do you know what the value of $\sum_{i=0}^{k-1}\frac 1{4^i}$ is? – abiessu Oct 17 '13 at 21:27
  • 1
    The sum you have written there is a partial sum of a geometric series. – John Martin Oct 17 '13 at 21:32
  • $\sum _{ i=0 }^{ k-1 }{ \frac { 1 }{ { 4 }^{ i } } } =\frac { 4 }{ 3 } (1-{ (1/4) }^{ \log { n } })$ which is a constant.

    So the answer is O(${ n }^{ 2 }$), right?

     – Chafic Oct 17 '13 at 21:54

1 Answers1

1

(Following your most recent comment of "$\sum _{ i=0 }^{ k-1 }{ \frac { 1 }{ { 4 }^{ i } } } =\frac { 4 }{ 3 } (1-{ (1/4) }^{ \log { n } })$ which is a constant...")

The geometric series with the first term $a=1$ and $r=\frac 14$ the common ratio between term $n$ and term $n+1$ has value

$$\sum_{i=0}^n {1-r^n\over 1-r}={1-\left(\frac 14\right)^i\over \frac 34}$$

This is non-constant as a function of $n$, however the limit as $n\to\infty$ is $\frac 43$ which is constant. Further, since the first term of the sequence is $1$, and since it is a sequence having all-positive terms, we have $t(n)=cn^2+t(1)$ where $c\in \left[1,\frac 43\right)$. Therefore the function $t(n)$ has order $O(n^2)$ as you have stated.

abiessu
  • 8,115