What complexity have a log(sum) shape?
cym13 via Digitalmars-d
digitalmars-d at puremagic.com
Tue Dec 8 13:33:58 PST 2015
On Tuesday, 8 December 2015 at 21:30:09 UTC, Charles 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.
No, his demonstration stands. This isn't about log algebra, it's
about asymptotic notation. I missed the fact that O(a+b) =
O(max(a, b)).
More information about the Digitalmars-d
mailing list