Suppose we have two algorithms A1 and A2 for solving the sam

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?

Solution

T1=aT(n/b)+f(n)

in t1 a=8;

b=2;

f(n)=n^2

so c=2;

by master theorm

c <log b base a

logb base a=3

so 2<3

T(n) = (n^Logba)

t(n)=n^3;

2) for t2

f(n)=n^2

c=2

log 63 base 4=2.9 approx

T(n) = (n^Logba)

t(n)=n^2.9

3)

we compare n^3 and n^2.9 then n^2.9 is faster hence t2(n) is faster