Question

Suppose you are choosing between the following 3 algorithms

Answer 1

Answer:

Answer: T(m) =3T (m/2) + 0 (m)

Explanation:

Algo A: Dividing into 3 sub problems and recurring for each with a combining step of linear time

T(m) =3T (m/2) + 0 (m)

Algo B: Dividing into 4sub problems with 1/4 size and solving each quadratic time

T(m) = 4{(m/4)²} + 0(m)

       = 0(m)² + 0(m)

    T(m) = 0(m²)

Algo C:

T(m) = 27(m/2) + 0(m)

Applying master theorem;

T(m) = a(T(m/b) + f(m)

log₂² = 1

mlogbᵃ = f(m)

Time complexity = 0(m x logm)

Also applying master theorem on Algo A;

m logbᵃ = m log₂³

f(m) = m

mlogbᵃ is greater than f(m)

Time complexity = mlog³₂