0
$\begingroup$

I am trying to solve a recurrence question using substitution method. The question looks like

enter image description here

But I am unable to solve it. Could you please help me to solve this question.

I assumed Let, T(m) <= cmloglog(m). This is the value I got using method https://stackoverflow.com/questions/12119799/solve-the-recurrence-tn-2tn-2n-logn. But I am unable to solve it for both O-notation and omega-notation. Could anyone please provide insights on how can i solve it ? Please let me know if I have to add any more information.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What do you mean by "I am unable to solve it for both O-notation and omega-notation"? Have you checked the answer with the highest votes in your link? $\endgroup$
    – xskxzr
    Commented Aug 20 at 3:04
  • $\begingroup$ Yes. So if we use induction method to prove this where we assume T(m) <= cmloglog(m) then with substituon method we get T(n) <= 2c(n/2)loglog(n/2) + (n/logn). I am unable to prove this is less than or equal to cnloglog(n). For O-notation. $\endgroup$
    – rozi
    Commented Aug 26 at 23:04

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.