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.

How can I solve the recurrence $$T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}\ ?$$

Please don't just write the name of the method, as I just started learning this stuff and things are a little hard for me to figure out on my own.

Thanks in advance.

share|improve this question
    
maybe you want some floor functions in that argument... –  BBischof Dec 28 '10 at 21:30
1  
Please don't undo formatting fixes that others have kindly done for you. –  Arturo Magidin Dec 28 '10 at 21:42
1  
A fundamental idea in this is the hierarchy of growth rates of functions. As n gets large, $(\log n)^a \lt x^b \lt c^x$, no matter how big a is and small b is (as long as it is >0) or how big b is and how small c is (as long as it is greater than 1). These also don't care if you multiply them by constants>0. Similarly $ax^b\le cx^d$ as long as $b\lt d$ regardless of a and c. These bounding relationships are used over and over again, so you need to get very comfortable with them. –  Ross Millikan Dec 28 '10 at 22:51

3 Answers 3

up vote 2 down vote accepted

As you are interested in large $n, \sqrt{n}\lt \frac{n}{a}$ for any $a$. So you can argue (assuming $T$ is increasing with $n$) that eventually $T(n) \leq T(\frac{2n}{3})+80$. This fits the method you have been using.

share|improve this answer
1  
@Ross Millikan: Should that be $T(\frac{2}{3}n) + 90$? –  Arturo Magidin Dec 28 '10 at 21:44
1  
@Arturo Magidin: I accept the n, but 80^2=6400. Fixed –  Ross Millikan Dec 28 '10 at 21:52
1  
@Ross Millikan: Oops, sorry about that; I think I read it at 8064 for some reason... –  Arturo Magidin Dec 28 '10 at 22:01
1  
@Bunny Rabbit: Just square both both sides: $n^2$ is eventually so much larger than $n$, that $\frac{n^2}{k}$ will eventually be larger than $n$ for any $k$. –  Arturo Magidin Dec 28 '10 at 22:08
1  
@Bunny Rabbit: In general, if $0\lt \alpha\lt \beta$, and $a,b$ are positive, then for sufficiently large $x$ you will always have $ax^{\alpha}\lt bx^{\beta}$. Just consider the quotient and let $x\to\infty$. It doesn't matter if $a$ is much larger than $b$, so long as $\beta$ is larger than $\alpha$ (even if just a little bit), the $\beta$-power will eventually "beat" the $\alpha$ power. Here you have $\alpha=\frac{1}{2}$ and $\beta=1$. –  Arturo Magidin Dec 28 '10 at 23:29

I believe Akra-Bazzi works for this and gives you $T(x) = \theta(\log x)$.

The recurrence you have satisfies the assumptions of Akra-Bazzi and we get $p=0$ (check out wiki for what $p$ is). $p=0$ implies $T(x) = \theta(\log x)$ in this case (as $g(x)$ is constant).

A more elementary proof would involve showing $T(x) = \mathcal{O}(\log x)$ as in Ross's answer, then try to show $T(x) = \Omega(\log x)$.


Here is an explanation of applying Akra-Bazzi to this one.

Akra-Bazzi is used to solve recurrences of the form:

$$ T(x) = g(x) + \sum_{i=1}^{m} a_i T(b_i x + h_i(x)) \ \text{where}\ x > x_0 $$

where $x$ is the variable, $a_i, b_i$ are constants.

In you case, we have that

$$T(x) = \sqrt{6046} + T(0.5 x + \sqrt{x})$$

Notice that, this corresponds to $\displaystyle m=1$.

The assumptions made by the theorem are

1) $\displaystyle a_i \gt 0$. This is true in your case, as $\displaystyle a_1 = 1$.
2) $\displaystyle 0 \lt b_i \lt 1$. This is true in your case, as $\displaystyle b_1 = 0.5$.
3) $\displaystyle |g(x)| = \mathcal{O}(x^c)$ for some $c$. In our case $\displaystyle g(x) = \sqrt{6046}$ is constant.
4) $h_i(x) = \mathcal{O}(\frac{x}{\log^2 x})$. In our case $h_1(x) = \sqrt{x} = \mathcal{O}(\frac{x}{\log^2 x})$ as $\displaystyle \log^2 x \le K \sqrt{x}$ for sufficiently large $\displaystyle x$.

There are a couple more, but are trivial to verify.

Now to apply Akra-Bazzi theorem, you need to find $\displaystyle p$ such that $\displaystyle \sum_{i=1}^{m} a_i (b_i)^p = 1$.

In our case, we get $\displaystyle 0.5^p = 1$ and so $\displaystyle p = 0$.

Once we find $\displaystyle p$, by the Akra-Bazzi theorem we have that

$$T(x) = \theta\left(x^p \left( 1 + \int_{1}^{x} \frac{g(t)}{t^{p+1}} \ \text{dt}\right)\right)$$

Since $\displaystyle p = 0$ and $\displaystyle g(t)$ is constant, we have that

$$T(x) = \theta\left(1 + \int_{1}^{x} \frac{\sqrt{6046}}{t} \ \text{dt}\right) = \theta(\log x)$$

I would also suggest you try to complete the elementary proof that $\displaystyle T(x) = \Omega(\log x)$. The relation $\displaystyle T(x) \leq T(2x/3) + 80$ only shows that $\displaystyle T(x) = \mathcal{O}(\log x)$.

The statement $\displaystyle T(x) = \theta(\log x)$ is stronger. For instance, $\displaystyle T(x) = 10$ also satisifies $\displaystyle T(x) \leq T(2x/3) + 80$, but it won't satisfy your original recurrence.

Hope that helps.

share|improve this answer

You can get precise asymptotics using $f(n)=n/2 \leq n/2 + \sqrt{n} \leq n/2 + \sqrt{n} + 1/2 = g(n)$. Iterates of $f(n)$ and $g(n)$ have a closed form.

The formulas for $f^k$ and $g^k$ (k'th iterates) imply that the number of iterations of $h(x)=x/2 + \sqrt{x}$ needed to bring $n > 4$ down into any interval $[0,C]$ with $C>4$, is $\log_2{n} + O(1)$.

From the recurrence, $T(n)$ increases by $\sqrt{6046}$ at each iteration, so the asymptotics are $T(n) = \sqrt{6046} \log_2(n) + O(1)$.

share|improve this answer

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.