Question

Suppose you are choosing between the following 3 algorithms

Algorithm A solves problems by dividing them into 3 subproblems of half size and then calling itself to solve each subproblem and combining the solution in linear time.

Algorithm B solves problems by dividing them into 4 subproblems of size 14 of the original and solving them with a different function that computes in quadratic time and combining the solution in linear time.

Algorithm C solves the problem by dividing them into 2 subproblems of half size and then calling itself to solve each subproblem and combining the solution in linear time.

a.) What recurrence represents run-time of each algorithm?
b.) Order the algorithms by their big-O from asymptotically smallest to largest, explain your reasoning. i.e. in order of their big-O

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³₂