497 views
2 votes
2 votes
  1.     T(n) =  3T(n/2) + $\sqrt[2]{n+3}$    if n > 1

                       =     d                        if n = 1

      2.      T(n) =   3T(n/2) + $\sqrt[2]{n^{4}+3}$   if n > 1

                     =     d if n = 1.

1 Answer

Best answer
2 votes
2 votes
To compute time complexity, we can ignore constant part, because it won't make a difference.
and I think it's 0 not d? It's a base case.
So we can re-write both expressions and then can apply Master's theorem:

$1. T(n)=3T(\frac{n}{2}) + n^{\frac{1}{2}} $      if n>1

a=3, b=2, f(n)=$n^{\frac{1}{2}} $

$n^{\log _{2}^{3}} > n^{\frac{1}{2}}$
Hence, T.C will be $ \Theta (n^{\log _{2}^{3}}) $

 

$2. T(n)=3T(\frac{n}{2}) + n^{2}  $  if n>1

$n^{2} > n^{\log _{2}^{3}} $

 Hence, T.C will be $\Theta(n^{2})$
selected by

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
2 answers
2
mdboi asked Oct 28, 2022
736 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
1 votes
1 votes
1 answer
3
1 votes
1 votes
1 answer
4
ItzDc asked Jun 3, 2022
2,841 views
I can't figure out how to proceed and which case it's falling under after calculating h(n)