Big-O-Notation mit zwei Variablen

Question

Dies stammt von Schreiben eines Programms zu find the median of two sorted arrays mit der Größe m bzw. n, mit der Komplexität der Zeit von O(log(m + n)).

Ich kann eine Lösung von O(log(m) + log(n)) erarbeiten. Erfüllt es die obige Zeitanforderung?

Ich denke, es positiv ist, weil:

log(m) + log(n) = log(m*n) <= log((m+n)^2) = 2*log(m+n) = O(log(m+n))

anders ausgedrückt, gibt es k = 2 und m0 = n0 = 1. Für jede m > m0 and n > n0 gibt es log(m*n) <= k*log(m + n).

Gibt es einen Fehler, oder bin ich richtig?

Allgemeiner ausgedrückt, können a, können wir log(n^a) = O(log(n)) mit der gleichen Argumentation sagen?

---

Dank Davids Antwort. Dies wird auch durch Big-O notation auf Wikipedia erwähnt:

"We may ignore any powers of n inside of the logarithms. The set O(log n) is exactly the same as O(log(n^c))."

Answer 1

Ja, Sie in jeder Hinsicht korrekt sind. Log wächst langsam genug, dass die asymptotische Klasse nicht sehr empfindlich auf die interne Funktion reagiert.