in Algorithms edited by
135 views
0 votes
0 votes
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
in Algorithms edited by
135 views

2 Comments

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

In the options log23 is raised to power of n.

0
0

1 Answer

0 votes
0 votes

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 nlog23 - 2kn (since nlog23 == 3log2n== 1)

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

similarly,

T(2)= 3klog23 - 2kn ( 3log2n == 3)

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

and so..on . so answer is B

by