Suppose we have two algorithms A1 and A2 for solving the same problem. Let T_1(n

Question

Suppose we have two algorithms A1 and A2 for solving the same problem. Let T_1(n) be the worst case time complexity of Algorithm A1 and T_2(n) be the worst case time complexity of Algorithm A2. We know that T_1(1) = 1 and T_1(n) = 8 middot T_1(n/2) + 100n^2. We also know that T_2(1) = 1 and T_2(n) = 63 middot T_2(n/4) + 200 middot n^2. Use the master method to decide T_1(n). Follow all the steps as illustrated in class (a, b, log_b a, etc). Use the master method to decide T_2(n). Follow all the steps as illustrated in class (a, b, log_b a, etc). For very large values of n, which algorithm is faster? Why?

Explanation / Answer

Answer:

Solution : Using Master's theorm

Here a = 8 b = 2 , f(n) = 100n^2 , c = 2

loga base b = log 8 base 2 = 3 , c < log a base b , therefore T1(n) = theta(n^c) = theta(n^2)

Therefore T1(n) = theta(n^2)

Using Masters Theorm

Here a = 63 , b = 4 , c = 2 , f(n) = 200n^2

Now loa a base b = loag 63 base 4 = 4

Here c < log a base b , therefore T2(n) = theta(n^2)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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