Liegt O(Wurzel n) * O(log n) in der Laufzeitklasse von O(n)

Question

Ich habe eine Schleife mit Wurzel-N Länge in der ein Algorithmus mit Log n Komplexität ausgeführt wird.

Liegt  und was kommt dabei genau raus?

Answer 1

> Schleife mit Wurzel-N Länge in der ein Algorithmus mit Log n Komplexität

Die Schleife hat dann eine  Laufzeit in O(√n · log n).

Zweite Ableitung von f(x) := √x · ln (x) ist f''(x) = - 1/4 · ln(x) / √x³

Für hinreichend große x ist ln(x) > 0 und √x³ > 0, also f''(x) < 0.

Der Graph von f ist also für hinreichend große x rechtsgekrümmt, wächst also langsamer als jede lineare Funktion.