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 ?

$\endgroup$
  • $\begingroup$ How do you define it for fractional $n/2$ and $\sqrt{n}$; what is the start value; and what exactly do you need to find? (Upper bound in the first case is obviously $+\infty$) $\endgroup$ – penartur Apr 12 '12 at 5:37
  • $\begingroup$ @penartur: ron clearly wants an $O(f(n))$ estimate on the rate of growth of $T(n)$. $\endgroup$ – Brian M. Scott Apr 12 '12 at 5:40
  • 1
    $\begingroup$ possible duplicate of how to solve $T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}$ $\endgroup$ – Aryabhata Apr 12 '12 at 5:59
  • $\begingroup$ That's nice , friend , thanks . I'll check it out . $\endgroup$ – JAN Apr 12 '12 at 6:03
  • 1
    $\begingroup$ note that 6.046 and 6.044 are course numbers. $\endgroup$ – zyx Apr 12 '12 at 6:05
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $T(8)=T(4)+2^8=T(2)+2^4+2^8=273\ne 2^9$. $\endgroup$ – Brian M. Scott Apr 12 '12 at 5:54
  • 1
    $\begingroup$ I quite agree that it’s $O(2^n)$, but I object to the statement that it ‘can be ... evaluated to $2^{n+1}$’, even if qualified by ‘for large $n$’: the statement is simply false. It can be bounded by $2^{n+1}$, which is something rather different. $\endgroup$ – Brian M. Scott Apr 12 '12 at 6:19
  • $\begingroup$ Oh sorry for that, I thought the sequence is $2^n+2^{n-1}+...$. $\endgroup$ – FiniteA Apr 12 '12 at 6:19
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So what do you recommend exactly ? use substitution ? $\endgroup$ – JAN Apr 14 '12 at 5:32
  • $\begingroup$ The estimate with $k$ levels of accuracy is from using the recurrence $k$ times to calculate $T(n)$ in terms of $T(m)$ where $m=n/{2^k}$ and using the bound $T(m) = O(2^m)$. $\endgroup$ – zyx Apr 14 '12 at 5:43
  • $\begingroup$ Let's see if I get you : take first $T(n/2)=T(n/4)+2^(n/2)$ and then : $T(n)=T(n/4) + 2^{n/2} + 2^{n}$ , and from that guess that we have : $T(n) = T(n/2^{k})$ + $\sum_{i=1}^n\ 2^{n/2^i}$ ? and then prove that recursion ? $\endgroup$ – JAN Apr 14 '12 at 6:06
  • $\begingroup$ Yes, and then apply the bound on $T(m)$ to replace $T(n/{2^k})$ by an $O()$ expression. $\endgroup$ – zyx Apr 14 '12 at 6:07
  • $\begingroup$ My guess is that the upper bound is (big O) $O(2^n)$ ? what do u think ? $\endgroup$ – JAN Apr 14 '12 at 6:12

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.