4
$\begingroup$

Given the Recurrences $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$

Remark : $T(n)=1$ for $n\le 3$

I'm trying to find their upper bound & lower bound , which is probably $O(2^n)$ for the first one.

I've tried to guess the solution for the first ($T(n)=T(n/2)+2^n$) but it doesn't work , afterwards I've tried the place $m = 2^n$ hence $n=\log(m)$ and use the new equation but still it won't work .

For the second ($T(n)=T(n/2+\sqrt n)+\sqrt{6044}$) I'm trying to guess that $T(n)=O(n)$ , hence $T(n)≤c\cdot n$ , but it still doesn't work.

Any hints and/or directions would be much appreciated .

Regards

EDIT:

About the second one :

$T(n)≤c(n/2+√n)+√6044=cn/2+c√n+√6044=(cn-cn/2)+c√n+√6044= cn-cn/2+c√n+√6044=cn-(cn/2-c√n-√6044) ≤^? cn$

Which is true only if $(cn/2-c√n-√6044)>0$ . What do you think , folks ?

  • 0
    @ron: constant does not matter2012-04-12

2 Answers 2

1

$T(n)=T(n/2)+2^n$ can be seen less than $2^{n+1}$, which is $O(2^n)$.

For the second one, notice that:

$T(n)=T(n/2+\sqrt{n})+\sqrt{6044}$

$\le n/2+\sqrt{n}+\sqrt{6044}$ since we guess it is linear

$\le n$ for larger $n$, because $\sqrt{n}$+constant grows slower than $n$.

  • 0
    Oh sorry for that, I thought the sequence is $2^n+2^{n-1}+...$.2012-04-12
0

A better estimate for the first one is $T(n) = 2^{n} + O(2^{n/2})$. Or the same idea iterated to give a chain of estimates like $T(n) = 2^n + 2^{n/2} + 2^{n/4} + O(2^{n/8})$.

  • 0
    There will not be a closed form. The only claim is the sum of the first $k$ terms of this series approximates $T(n)$ to within $O(n/{2^k})$.2012-04-14