int func(int n){
       if(n==1)
         return 0;
       else
         return sqrt(n);
    }

Wobei sqrt (n) eine C math.h-Bibliotheksfunktion ist.

O (1)O (lg n)O (lg lg n)Auf)

Ich denke, dass die Laufzeit völlig vom sqrt (n) abhängt. Ich weiß jedoch nicht, wie diese Funktion tatsächlich implementiert ist.

P.S. Der allgemeine Ansatz, um die Quadratwurzel einer mir bekannten Zahl zu finden, ist die Newtonsche Methode. Wenn ich mich nicht irre, ist die zeitliche Komplexität nach Newtons Methode O (lg n). Sollte die Antwort also O (lg n) sein?

P.P.S. Ich habe diese Frage in einem kürzlich durchgeführten Test erhalten, für den ich erschienen bin.