On Friday, 16 February 2018 at 19:40:07 UTC, H. S. Teoh wrote:
On Fri, Feb 16, 2018 at 07:40:01PM +0000, Ola Fosheim Grøstad
via Digitalmars-d wrote:
On Friday, 16 February 2018 at 18:16:12 UTC, H. S. Teoh wrote:
> The O(N) vs. O(n) issue is actually very important once you
I understand what you are trying to say, but this usage of
notation is
very confusing. O(n) is exactly the same as O(N) if N relates
to n by
a given percentage.
N = size of DAG
n = size of changeset
It's not a fixed percentage.
Well, for this comparison to make sense asymptotically you have
to consider how n grows when N grows towards infinity. Basically
without relating n to N we don't get any information from O(n) vs
O(N).
If you cannot bound n in terms of N (lower/upper) then O(n) is
most likely either O(1) or O(N) in relation to N... (e.g. there
is a constant upper limit to how many files you modify manually,
or you rebuild roughly everything)
Now, if you said that at most O(log N) files are changed, then
you could have an argument in terms of big-oh.
