Brauche hilfe der der LAufzeit eines rekursiven Algorithmus

  • Hallo zusammen,
    bin neu hier. Habe Probleme die laufzeit eines rekursiven Algorithmus zu bestimmen.
    Hier die Methode

    public static <T extends Comparable<T>> boolean myAlgo(T x, T[] array, int l, int r){
    if(r-l==1){
    return (array[l].compareTo(x)==0);
    }else{
    int m = (l+r)/2;
    return (myAlgo(x, array, l, m) || myAlgo(x, array, m, r));
    }
    }

    Ich weiß, was er tut, jedoch nicht wie ich die worst case Laufzeit bestimmen soll.
    Für die erste if Anweisung sollte das ja O(1) sein, falls r-l == 1 ist und x = array[l] ist.
    Bei int m hätte ich gedacht das es eine Laufzeit von log_2 (n) hat. Danach haben ich keine Ahnung mehr.
    Außerdem muss r ungleich l sein, sonst endet das in einer Endlosschleife.

    Ich hoffe ihr könnt mir helfen.

    LG Cris

  • würde auf O(n) tippen, da es bis zu 2 Rekursionsaufrufe pro Durchlauf gibt (-> O(2^n)), aber n sich pro Aufruf halbiert (-> O(logn))
    => O(n)

    bin mir aber nicht sicher, ist schon zu lange her

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!