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
    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$)2012-04-12
  • 0
    @penartur: ron clearly wants an $O(f(n))$ estimate on the rate of growth of $T(n)$.2012-04-12
  • 1
    possible duplicate of [how to solve $T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}$](http://math.stackexchange.com/questions/15769/how-to-solve-t-n-t-left-fracn2-sqrtn-right-sqrt6046)2012-04-12
  • 0
    That's nice , friend , thanks . I'll check it out .2012-04-12
  • 1
    note that 6.046 and 6.044 are course numbers.2012-04-12
  • 0
    One thing is not clear to me , how much does it matter the difference between 6044 & 6046 in the SQRT ?2012-04-12
  • 0
    @ron: constant does not matter2012-04-12

2 Answers 2