Beiträge von cris318

  • 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