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

Improve this question
$\endgroup$
7
  • $\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, 2014 at 10:17
  • $\begingroup$ What did your friend get? $\endgroup$
    – gardenhead
    Jun 17, 2014 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, 2017 at 17:04
  • $\begingroup$ The first recurrence is not of a form that can be solved with the Master theorem. $\endgroup$
    – Raphael ♦
    Sep 27, 2017 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, 2017 at 21:37

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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