Aufgabe:
Binäre Exponentiation - Laufzeitanalyse.
Zu zeigen: Worstcase Laufzeit Binäre Exponentiation (rekursiv definiert) soll Ο(log(n)) sein.
Als Hinweis ist folgendes angegeben: Hinweis: Sie können zunächst eine Rekursionsgleichung T(n) = ... aufstellen und dann durch vollständige Induktion eine obere Schranke auf T(n) zeigen.
Aloha :)
Wenn du das als Iteration schreibst:
double power(double x, unsigned n) { double p= 1.0; while (n) { p*= (n&1) ? x : 1; n>>= 1; x*= x; } return p;}
ist sofort klar, dass die Schleife maximal \(\lceil\log_2(n)\rceil\) Mal durchlaufen wird.
