Notazione Big-O con due variabili

Question

Questo deriva dalla scrittura di un programma in find the median of two sorted arrays con dimensioni m e n rispettivamente, con la complessità temporale di O(log(m + n)).

Posso elaborare una soluzione di O(log(m) + log(n)). Soddisfa i requisiti di tempo sopra indicati?

penso che sia positivo perché:

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

In altre parole, esistono k = 2 e m0 = n0 = 1. Per qualsiasi m > m0 and n > n0, c'è log(m*n) <= k*log(m + n).

C'è un difetto o sono corretto?

Più generalmente, data costante a, possiamo dire log(n^a) = O(log(n)) con lo stesso ragionamento?

---

Grazie alla risposta di David. Questo è anche menzionato da Big-O notation su Wikipedia:

"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

Sì, siete sulla strada giusta su tutti i fronti. Il registro cresce abbastanza lentamente che la classe asintotica non è molto sensibile alla funzione interna.