Question

what is the complexy of t(n)=3t(n/2)+n

Answer 1

The given recurrence is  T(n)=3T(n2)+c , where  c  is assumed to be a constant. Also assuming base cases of  T(0)=T(1)=1  

I hope to show different methods of solving this recurrence, purely for illustrative purposes. I wish to state at this point that, if you know the Master theorem, that would be the simplest (and in some sense, “best”) way to solve this recurrence (and similar ones).

Solution using the “Iteration” method:

This is perhaps the simplest (not necessarily the most efficient or useful) method to solve not-so-complex recurrences by repeatedly substituting the sub-expressions for  T(m),m<n  in the original expression for  T(n) , as shown below. After a few substitutions, we can try to “eyeball” some pattern in the expressions obtained after each “level” of substitutions, and then use that to write an expression for  T(n)  in which the substitution has been done in “full” — that is, till the base case.

T(n)=3T(n/2)+c=9T(n/4)+4c=27T(n/8)+13c=⋯=3kT(n/2k)+(1+3+9+…+3k−1)c  

Now, suppose  n=2m , hence  m=log2n  

T(n)=3mT(1)+(1+3+…+3m−1)c=3m+1(3m−1)3−1c=(1+12c)3m−1

Hope this helps you ♥

Mark my answer as brainliest please.