Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
1  
    
That's nice , friend , thanks . I'll check it out . –  ron Apr 12 '12 at 6:03
1  
note that 6.046 and 6.044 are course numbers. –  zyx Apr 12 '12 at 6:05

2 Answers 2

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

share|improve this answer
    
$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
1  
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})$.

share|improve this answer
    
So what do you recommend exactly ? use substitution ? –  ron 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 ? –  ron 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 ? –  ron Apr 14 '12 at 6:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.