# Recurrence $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$ , without (!) the master method

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:

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

• 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$) – penartur Apr 12 '12 at 5:37
• @penartur: ron clearly wants an $O(f(n))$ estimate on the rate of growth of $T(n)$. – Brian M. Scott Apr 12 '12 at 5:40
• possible duplicate of how to solve $T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}$ – Aryabhata Apr 12 '12 at 5:59
• That's nice , friend , thanks . I'll check it out . – JAN Apr 12 '12 at 6:03
• note that 6.046 and 6.044 are course numbers. – zyx Apr 12 '12 at 6:05

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

• $T(8)=T(4)+2^8=T(2)+2^4+2^8=273\ne 2^9$. – Brian M. Scott Apr 12 '12 at 5:54
• 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. – Brian M. Scott Apr 12 '12 at 6:19
• Oh sorry for that, I thought the sequence is $2^n+2^{n-1}+...$. – FiniteA Apr 12 '12 at 6:19

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

• So what do you recommend exactly ? use substitution ? – JAN Apr 14 '12 at 5:32
• 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)$. – zyx Apr 14 '12 at 5:43
• 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 ? – JAN Apr 14 '12 at 6:06
• Yes, and then apply the bound on $T(m)$ to replace $T(n/{2^k})$ by an $O()$ expression. – zyx Apr 14 '12 at 6:07
• My guess is that the upper bound is (big O) $O(2^n)$ ? what do u think ? – JAN Apr 14 '12 at 6:12