1

Can someone tell me what am i doing wrong here ? My base case i.e. T(4)=12 

T(n)=2T(n/2)+8n , T(4)=12

=2^(2)*T(n/2^2)+2*8n

=2^(i)*T(n/2^i)+i*8n

so let, n/2^(i) = 4 so, i=lgn-2

=2^(lgn-2)12 + (lgn-2) 8n
jon
  • 111
  • 1
    Hint: T(n) = n[8*ln(n)/ln(2) - 13]. (Upvote for correct SE site :) ) If it doesn't evaluate correctly for the initial conditions provided, it's not the correct solution. – Cloud Feb 25 '16 at 02:10
  • @Dogbert your hint is right but my last step that i havewritten is wrong. – jon Feb 25 '16 at 02:22
  • @Dogbert In other words may i know how do i proceed from there ? – jon Feb 25 '16 at 02:38
  • Check out question (4)(c) here: https://cseweb.ucsd.edu/classes/wi14/cse21-a/solution6.pdf It's almost identical to what you're solving. You're missing a few steps it seems. If this solves your problem, consider posting the answer yourself to this site so future readers can benefit from your experience. – Cloud Feb 25 '16 at 03:03
  • Were you able to solve your problem? – Cloud Feb 26 '16 at 02:19
  • @Dogbert yes sir so the the value of of 2^(lgn-2)=n/2 and from there i was able to get the result – jon Feb 26 '16 at 19:32
  • Great. If that's the case, it would be a nice thing for the community if you posted your updated/full solution, or deleted the question, so others benefit from it, or we just reduce clutter. Cheers! – Cloud Feb 26 '16 at 19:42

0 Answers0