A recursive algorithm has been created which will divide a problem into 4 equal

Question

A recursive algorithm has been created which will divide a problem into 4 equal sub problems by doing n1/2 amount of work, where n is the size of the problem. This recursive algorithm solves the subproblems using the same process. The amount of work to solve a problem of size 1 is 0. This problem has three parts: Write the recurrence equation. Solve the recurrence relation without using the master theorem. Check your solution by using the master theorem.

So, T(1) = 0, the n1/2 is throwing me off here... Any help would be great!

Explanation / Answer

The n1/2 is the amount of work required at each stage to split the problem into subproblems. So it's the second term in the recurrence:

T(n) = 4T(n/4) + n1/2.

To solve this recurrence by substitution, we make a "guess." Our guess will be that T(n) = O(n).

To prove this, we have to show that T(n) cn for sufficiently large c.

T(n) = 4cn/4 + n1/2 = cn + n1/2. This can never be cn, so we will redo it while subtracting a lower-order term (which does not affect the asymptotic analysis).

T(n) cn - dn1/2

Now:

T(n) = 4(cn/4 - d(n/4)1/2)) +n1/2 = cn - 4dn1/2/2 + n1/2 = cn - 2dn1/2 + n1/2

T(n) = cn - (2dn1/2 - n1/2)

Which means that T(n) cn as long as (2d-1)n1/2 0. We choose d 1/2 and then our recurrence is satisfied.

By Master Theorem, a = 4, b = 4, logba = log44 = 1 so n1=n. Since n > n1/2, we are in case 1 so T(n) = O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.