[LUGOS-PROG] Casovna zahtevnost

[gregor.berginc na guest.arnes.si]

Zivjo

> Kako bi vi izracunali casovno zahtevnost te funkcije? Funkcija torej
> vrne starsa nekega nodea x, v drevesu s korenom root. Aja, to je
> binarno iskalno drevo.

Nekaj casa je ze preteklo odkar sem poslusal APS, ampak jest bi rekel, da
je O(log_2(n)). Ce me spomin ne vara, potem ima iskanje poljubnega
elementa dvojiskega drevesa isto zahtevnost. Tisto, kar ti zgornja
funkcija naredi je zgolj to, da se ustavi en nivo prej, kar pa za funkcijo
O nima pomena. Tudi tista tri preverjanja pred zadnjo vrstico so
nepomembna.

lp,
Grega