बिग-ओ नोटेशन दो चर के साथ

Question

यह की जटिलता के साथ क्रमशः m और n आकार के साथ एक प्रोग्राम लिखने से find the median of two sorted arrays पर शुरू होता है।

मैं O(log(m) + log(n)) का समाधान निकाल सकता हूं। क्या यह उपरोक्त समय आवश्यकता को पूरा करता है?

मुझे लगता है कि यह सकारात्मक है क्योंकि:

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

दूसरे शब्दों में, वहाँ k = 2 और m0 = n0 = 1 मौजूद हैं। किसी भी m > m0 and n > n0 के लिए, log(m*n) <= k*log(m + n) है।

क्या कोई दोष है, या मैं सही हूँ?

अधिक आम तौर पर, a को देखते हुए, क्या हम एक ही तर्क के साथ log(n^a) = O(log(n)) कह सकते हैं?

---

डेविड के जवाब के लिए धन्यवाद। यह भी विकिपीडिया पर Big-O notation से उल्लेख किया गया है:

"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

हाँ, आप सभी मामलों में सही कर रहे हैं। लॉग धीरे-धीरे बढ़ता है कि एसिम्प्टोटिक कक्षा अंदर के फ़ंक्शन के प्रति बहुत संवेदनशील नहीं है।