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.