3
$\begingroup$

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)$$

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – abiessu Oct 17 '13 at 21:27
  • 1
    $\begingroup$ The sum you have written there is a partial sum of a geometric series. $\endgroup$ – John Martin Oct 17 '13 at 21:32
  • $\begingroup$ $\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? $\endgroup$ – Chafic Oct 17 '13 at 21:54
1
$\begingroup$

(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.

| cite | improve this answer | |
$\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.