Divide and Conquer
Hello,
I tried to understand this piece of algorithm anlysis through slides and youtube but I can't understand the part that why we multiplied T(N/2) with 4 and why it is N/2 not N at the end?
X = a 2N/2 + b
Y = c 2N/2 + d
XY = ac 2N + (ad+bc)2N/2+bd
Mult(X,Y):
if |X| = |Y| = 1 return (XY);
Break X into a:b and Y into c:d;
return ( Mult(a,c)·2N + (Mult(a,d) + Mult(b,c)) ·2N/2 +
Mult(b,d));
T(1) = k for some constant k
T(N) = 4 T(N/2) + k’ N for some constant k’
I tried to understand this piece of algorithm anlysis through slides and youtube but I can't understand the part that why we multiplied T(N/2) with 4 and why it is N/2 not N at the end?
X = a 2N/2 + b
Y = c 2N/2 + d
XY = ac 2N + (ad+bc)2N/2+bd
Mult(X,Y):
if |X| = |Y| = 1 return (XY);
Break X into a:b and Y into c:d;
return ( Mult(a,c)·2N + (Mult(a,d) + Mult(b,c)) ·2N/2 +
Mult(b,d));
T(1) = k for some constant k
T(N) = 4 T(N/2) + k’ N for some constant k’
Topic archived. No new replies allowed.