2
$\begingroup$

I am working on proving the time complexity for the following problem, but believe I am stuck:

$$T(n) = 2T(n/3 + 1) + n$$

I have checked out this link here on time complexity on cs.stackexchange

However, I still cannot seem to find the answer. Using this proof from a Dartmouth course:

$a = 2, b = 3, c = 1$

In this case, I know logb a is .63, which is less than 1, so the complexity is $Θ(n)$. However, I don't know how to prove that.

I am trying to practice with the methods that I "know" - Master Theorem, Substitution, Iteration, or a Recursion Tree. And using one of those 4 methods, I can't find a way to prove the complexity is $Θ(n)$, even though I know that's the answer.

Would anyone be able to assist?

$\endgroup$
  • 1
    $\begingroup$ You can use the Akra–Bazzi theorem, a generalization of the master theorem. $\endgroup$ – Yuval Filmus Sep 20 '18 at 3:43
  • $\begingroup$ Hi @YuvalFilmus , thank you for the suggestion. I read through the page that you hyperlinked but can't see how this algorithm is solvable by Akra-Bazzi. $\endgroup$ – Jerry M. Sep 20 '18 at 15:28
  • $\begingroup$ Recurrence relations don't have time complexities! Recurrences are simply sets of equations which have a solution, and that solution is a function. Suppose instead that you're told that apples cost $a$ and pears cost $p$. Asking for the time complexity of a recurrence is like asking for the cost of the equations $4a+2p=8$, $3a+3p=9$. The solutions to those equations tell you the cost of the things, but it makes no sense to ask about the "cost" of the equations. $\endgroup$ – David Richerby Sep 21 '18 at 11:20
  • $\begingroup$ Also, you're not trying to "solve an algorithm by Akra-Bazzi". The thing you're trying to solve is a recurrence relation; an algorithm is a sequence of instructions for performing some task. $\endgroup$ – David Richerby Sep 21 '18 at 11:22
2
$\begingroup$

You can use the Akra–Bazzi theorem, a generalization of the master theorem.

Using the notations in the Wikipedia page:

  • $g(x) = x$
  • $k = 1$
  • $a_i = 2$
  • $b_i = 1/3$
  • $h_1(x) = 1$ (in fact, probably $h_1(x)$ is a bit different, since $n/3+1$ isn't always an integer)
  • $x_0$ is a constant which is missing from your recurrence relation

You can easily check that all conditions of the theorem hold. To get the asymptotics, we first compute the value of $p$, which is the solution to $2(1/3)^p = 1$, that is, $p = \log_3 2$. Next, we calculate the integral appearing in the answer formula: $$ \int_1^x \frac{u}{u^{p+1}} \, du = \int_1^x u^{-p} \, du = \frac{x^{1-p}-1}{1-p}. $$ We conclude that $$ T(x) = \Theta\left(x^p\left(1 + \frac{x^{1-p}-1}{1-p}\right)\right) = \Theta(x^p + x) = \Theta(x^{\max(p,1)}). $$ Since $p < 1$, the answer is $T(x) = \Theta(x)$.

More generally, the Akra–Bazzi theorem shows that the master theorem applies even when the applications of $T$ on the right-hand side of the recurrence are off by a small amount (at most $O(x/\log^2 x)$).

$\endgroup$
1
$\begingroup$

You could try to show by induction that T(n) ≤ 5n. We have T(n) = 2 T (n/3 + 1) + n ≤ 10(n/3 + 1) + n = 4 1/3 n + 10 ≤ 5n if n ≥ 15, so if you show T(k) ≤ 5k for some range n/3 ≤ k < n, n ≥ 15, the problem is solved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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