Ace Algorithms

Question

If k is a positive constant, then the following divide and conquer recurrence evaluates to?

T(n) = k ; n=1

T(n) = 3 T (n/2) + kn ;n>1

a)T(n)= 3kn2-kn

b)T(n)=3kn log23  - 2kn

c)T(n)=3knlog23 - kn

d)T(n)=3kn2-2knlog23

Comments

can u please make options more clearer and even option B and C are same.

---

In the options log₂3 is raised to power of n.

Answer 1

since , T(1)=K (given)

T(2)=3T(1)+2K=5K

T(4)=3T(2)+4k=19K ....  SO...on

putting these values in option 2...

T(1)= 3k n^log₂3 - 2kn (since n^log₂3 == 3^log₂n== 1)

   =3*k*1 - 2k*1 == k

similarly,

T(2)= 3k^log₂3 - 2kn ( 3^log₂n == 3)

       = 3*k*3 - 2*k*2 = 5k

and so..on . so answer is B