Ich kann nur C(SK_f) <= n*(2^(n+1)) - 1 zeigen.
Habe ich irgendwas übersehen?
Danke

Das gleiche gilt für
depth<= floor(log_2 n) + n + 1

Beide ergebnisse entstanden nach einer Worstcase-Analyse.

Freu mich auf Hinweise!
Danke

Hmm... es ist ziemlich schwer nur anhand deines Ergebnisses zu beurteilen, ob du was übersehen hast. Und ein posten deiner Lösung hier wäre nicht wirklich angebracht.
Irgendwo wirst du in deiner Betrachtung ein Gatter zuviel genommen haben. Überleg dir vielleicht nochmal für (sehr) kleine n (2 oder 3) an konkreten Beispielen inwieweit das mit deine Analyse übereinstimmt.

Gelöst!

Danke für den Hinweis.
Bei der Berechnung der Kosten hatte ich auch die Not-Gatter betrachtet. Jetzt passt es.

Ist es ein Schreibfehler, dass bei depth(SK_f) der Zehnerlogarithmus (log) steht und nicht log_2?

Jan Alexander schrieb:
-------------------------------------------------------
> Ist es ein Schreibfehler, dass bei depth(SK_f) der
> Zehnerlogarithmus (log) steht und nicht log_2?

Das ist kein Fehler. Man sollte sich in der Informatik an folgendes gewöhnen: wenn nur "log" dasteht, ist i.d.R. der Zweierlogarithmus gemeint ist. Es ist also eher so, dass ein Zehnerlogarithmus als solcher explizit gezeichnet wird.

In der Aufgabe ist also log_2 gemeint... hätte man vielleicht, um Unklarheiten zu vermeiden, auch hinschreiben können... aber... siehe oben.