Induktion
Posted: 01/11-2007 11:13
Hej!
Jag vill gärna ha hjälp med detta problem.
Låt M(n) beteckna antalet bit-operationer som behövs för att multiplicera två n-bitars heltal. Man kan visa att
M(2n)<=3M(n)+Cn,
där C är en positiv konstant.
Visa med hjälp av denna olikhet och induktion att för k>=1 gäller
M(2^k)<=B(3^k - 2^k),
där B=max(M(2),C)
Tack på förhand.
varberg0
[/sub]
Jag vill gärna ha hjälp med detta problem.
Låt M(n) beteckna antalet bit-operationer som behövs för att multiplicera två n-bitars heltal. Man kan visa att
M(2n)<=3M(n)+Cn,
där C är en positiv konstant.
Visa med hjälp av denna olikhet och induktion att för k>=1 gäller
M(2^k)<=B(3^k - 2^k),
där B=max(M(2),C)
Tack på förhand.
varberg0
[/sub]