CODEWITHSUNDEEP
algorithmbig-o
Eric Z
Eric Z

Reputation: 14505

Big-O notation with two variables

This originates from writing a program to find the median of two sorted arrays with size m and n respectively, with the time complexity of O(log(m + n)).

I can work out a solution of O(log(m) + log(n)). Does it meet the time requirement above?

I think it's positive because:

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

Put another way, there exist k = 2 and m0 = n0 = 1. For any m > m0 and n > n0, there is log(m*n) <= k*log(m + n).

Is there a flaw, or am I correct?

More generally, given constant a, can we say log(n^a) = O(log(n)) with the same reasoning?

Thanks to David's answer. This is also mentioned by Big-O notation on 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))."

Upvotes: 8

Views: 4421

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Yes, you're correct on all counts. Log grows slowly enough that the asymptotic class isn't very sensitive to the function inside.

Upvotes: 6

Related Questions