On Tue, Dec 08, 2015 at 09:30:09PM +0000, Charles via Digitalmars-d wrote: > On Tuesday, 8 December 2015 at 20:56:28 UTC, cym13 wrote: > >On Tuesday, 8 December 2015 at 17:33:49 UTC, Andrei Alexandrescu wrote: > >>On 12/08/2015 12:12 PM, Timon Gehr wrote: > >>>O(log(n+m)) = O(log(n)+log(m)). > >> > >>Noice. Yes I did miss it. Thx!! -- Andrei > > > >Surely I'm missing something obvious but why is it true exactly? > > Im confident it isn't. I think the rule he was thinking of was > O(log(ab)) = O(log(a)+log(b)), which is just a basic property of > logarithms. It's pretty easy to get to a contradiction between those > two rules.
There is no contradiction. Big-O notation deals with asymptotic behaviour as the variables approach infinity, so behaviour at 'small' values of m and n are irrelevant. The idea is that if m grows fundamentally faster than n, then for sufficiently large values of m and n, the actual value will be dominated by m, and the contribution from n will be negligible. The same argument holds for the converse. Hence, O(n+m) = O(max(n,m)). Now, for O(log(n+m)), at sufficiently large values of n and m what dominates the argument to log will be max(n,m), so O(log(n+m)) = O(log(max(n,m))). But we've already established that O(f(x)+g(x)) = O(max(f(x),g(x))), so we note that O(log(max(n,m))) = O(max(log(n),log(m))) = O(log(n)+log(m)). Note that the last step only works for slow-growing functions like log, because log(x+y) < log(x) + log(y). This is no longer true for functions that grow too fast, e.g., exp(x+y) < exp(x) + exp(y) is false, so big-O expressions involving exp cannot be simplified in this way. T -- We've all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the Internet, we know this is not true. -- Robert Wilensk