5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ maybe you want some floor functions in that argument... $\endgroup$
    – BBischof
    Dec 28, 2010 at 21:30
  • 1
    $\begingroup$ Please don't undo formatting fixes that others have kindly done for you. $\endgroup$ Dec 28, 2010 at 21:42
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 28, 2010 at 22:51

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ @Ross Millikan: Should that be $T(\frac{2}{3}n) + 90$? $\endgroup$ Dec 28, 2010 at 21:44
  • 1
    $\begingroup$ @Arturo Magidin: I accept the n, but 80^2=6400. Fixed $\endgroup$ Dec 28, 2010 at 21:52
  • 1
    $\begingroup$ @Ross Millikan: Oops, sorry about that; I think I read it at 8064 for some reason... $\endgroup$ Dec 28, 2010 at 22:01
  • 1
    $\begingroup$ @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$. $\endgroup$ Dec 28, 2010 at 22:08
  • 1
    $\begingroup$ @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$. $\endgroup$ Dec 28, 2010 at 23:29
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .