1
$\begingroup$

I had my final exam today in an advanced algorithms course. In it there were two recurrence relations and I used the Akra-Bazzi theorem to solve them. After the examination I was discussing the problem with one of my colleagues and they apparently got a different bound using Master theorem. My question is which of this two bounds are tighter?

The recurrences were:

$1)\quad T(n) = 8T\left(\frac{(2n-1)}{4}\right)+n^3+n\log n$

$2)\quad T(n) = 3T(n/2)+n\log^2 n $

Now, correct me if I'm wrong but Akra-Bazzi gives 1) as $\Theta(n^3\log n )$ and 2) as $\Theta(n\log^2 n )$ Can somebody please verify 2) by Akra-Bazzi? I checked and regularilty condition doesn't hold for 2) .

$\endgroup$
  • $\begingroup$ Doing it back-of-the-envelope (literally actually), shouldn't the answers be 1) $\Theta(n^{3})$ and 2) $\Theta(n^{\log_{2}(3)})$ (from both methods, though the first one is not normally dealt with by the Master Theorem as I would recognise it). $\endgroup$ – Luke Mathieson Jun 16 '14 at 10:17
  • $\begingroup$ What did your friend get? $\endgroup$ – gardenhead Jun 17 '14 at 3:53
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Sep 27 '17 at 17:04
  • $\begingroup$ The first recurrence is not of a form that can be solved with the Master theorem. $\endgroup$ – Raphael Sep 27 '17 at 17:05
  • $\begingroup$ @Raphael you're mistaken. One can see that the master theorem is clearly applicable in two ways. 1) For large n, the -1/4 term is "negligible" since the master theorem provides an asymptotic solution for the recurrence, so it can be treated with an equation without it and one can proceed from there. 2) one can make a substitution such as u = 2n+1 alter the recurrence and proceed from there. I believe Yuval saw this (since he correctly answered the question). $\endgroup$ – user119264 Oct 4 '17 at 21:37
1
$\begingroup$

Both methods give $\Theta$ type estimates. That is, the master theorem gives some estimate $T = \Theta(f)$, and the Akra–Bazzi theorem gives some estimate $T = \Theta(g)$. From the definition of $\Theta$ it immediately follows that $f = \Theta(g)$ and $g = \Theta(f)$, that is, the estimates are equivalent. I suspect either one of you was mistaken, or both bounds that you got, while seemingly different, are in fact equivalent.

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