Was ist die Garantie dafür, dass Little-O eine strenge Obergrenze ist?

Question

Ob das kleine o eine enge Obergrenze oder eine strenge Obergrenze ist?

Korrigieren Sie die Antwort unten, wenn falsch,

g(x) ist eine obere Schranke für f(x) die nicht asymptotisch dicht ist. Es gibt eine viel größere Lücke zwischen den Wachstumsraten von f and g wenn f ∈ o(g) als wenn f ∈ O(g).

Big-O ist zu wenig-o als ≤ zu <. Big-O ist eine inklusive Obergrenze, während Little-O eine strenge Obergrenze ist.

Reicht das nicht aus, um eine strenge Obergrenze zu garantieren?

Answer 1

Ihre Intuition sieht korrekt aus, aber ich bin mir nicht sicher, ob Sie Begriffe verwenden.

Aus Wikipedia: big-O vs little-o

Auf diese Weise macht wenig-o-Notation eine stärkere Aussage als die entsprechenden Big-O-Notation: jede Funktion, die wenig-o von g ist, ist auch Big-O von g, aber nicht jede Funktion, die groß-O von g ist auch wenig-o von g (zum Beispiel ist g selbst nicht, es sei denn, es ist gleich Null in der Nähe von ∞).

Ein weiteres nützliches Zitat:

die Beziehung f (x) = o (g (x)) entspricht
lim (f (x)/g (x)) = 0 (wenn x -> ∞)
vs
die Beziehung f (x) = O (g (x)) entspricht
lim (f (x)/g (x)) < ∞ (wenn x -> ∞)