Laufzeit von Funktion (Binärbaum)

[WarSlash]

Ich habe bisschen programmiert und stelle mir nun die Frage, welche Laufzeit, der untere Code mir erzeugt:
Die Funktion soll die Höhe eines Binärbaums ausgeben.
int hoehe(binbaum b)
{
if (b == NULL) /* Baum ist leer: Hoehe einfach -1 */
return -1;
else return 1+maximum(hoehe(b->linker_sohn),hoehe(b->rechter_sohn));
}


Ich meine, dass das Worst, Best und Average Case alle O(n-1) sind!
Der Algorithmus traversiert den ganzen Baum. Wenn der Baum eine lineare Liste ist, dann ist es eh O(n-1). Auch im ausgeglichen Fall, scannt er den ganzen Baum.

Bin mir aber nicht sicher! Wie sieht ihr das?

[Senior Sanchez]

Das sollte von O(n) sein.

O(n-1) haste sicherlich angenommen, weil man die Wurzel ja nicht beim traversieren "besichtigt", aber die O-Notation spricht ja für n -> ziemlich ziemlich groß (also unendlich eigentlich) und da fällt das -1 nicht ins Gewicht.

[Der_Donnervogel]

Ich sehe das auch so. Da jeden Knoten immer genau einmal besucht und immer der ganze Baum traversiert wird, wächst die Laufzeit linear mit der Anzahl der Knoten und ist somit O(n). Das -1 kann man bei der O-Notation weg lassen.

[WarSlash]

Gut^^. Da lag ich da fast richtig!

[Trap]

O(n) ist äquivalent O(n-1) oder auch O(2n-17). Genauso wie 1 äquivalent 0,99999 oder 439/439...

Man braucht da nicht unterscheiden, es ist nur unüblich etwas anderes als O(n) zu schreiben. Auch O(17n-999999!) wäre mathematisch richtig ;)
Allerdings benutzen manche nicht die mathematische Definition der Landau-Symbole, sondern irgendwas informelles in dem die Vorfaktoren oder Summanden auch eine Bedeutung haben.