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

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
    $T(8)=T(4)+2^8=T(2)+2^4+2^8=273\ne 2^9$.2012-04-12
  • 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.2012-04-12
  • 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
    So what do you recommend exactly ? use substitution ?2012-04-14
  • 0
    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)$.2012-04-14
  • 0
    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 ?2012-04-14
  • 0
    Yes, and then apply the bound on $T(m)$ to replace $T(n/{2^k})$ by an $O()$ expression.2012-04-14
  • 0
    My guess is that the upper bound is (big O) $O(2^n)$ ? what do u think ?2012-04-14
  • 0
    and I think that the $i$ of the $\sum$ that I wrote in the previous comment , should run from $1$ to $k$ , and not from $1$ to $n$ , right ?2012-04-14
  • 0
    i think there's a problem with the way u suggested : now I have $T(n)=T(n/2^k )$ + $\sum _{i=1}^k {2^{(n/2^i )}} $ , and if $m=n/2^k$ , there's a problem with the $\sum$ , since it uses $i$ and not $k$ .... Am I right ?2012-04-14
  • 0
    The $i$ is a notational device (a "dummy variable" or "index") used to express the terms of a sum that depends only on $n$ and $k$. Your expression is T(n) = (one function of n and k) + (another function of n and k) with the second one involving Sigma notation and the letter $i$ but the latter are notational or typographical details. You could have written the second function as an explicit sum of $k$ terms (each depending only on $n$) without any summation symbol or the letter $i$.2012-04-14
  • 0
    Indeed , but I still have a $\sum$ , I can't escape from it , I think ......2012-04-14
  • 0
    I'm sorry my friend but I can't find any actual form of Series of $\sum_{i=0}^k 2^{n/{2^i}}$2012-04-14
  • 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