Complexity nomenclature

[H. S. Teoh via Digitalmars-d]

On Fri, Dec 04, 2015 at 01:37:06PM -0500, Andrei Alexandrescu via Digitalmars-d wrote:
> On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
[...]
> Here's the algebra.
> 
> Terms:
> 
> 1 = O(1)
> log = O(log n)
> plog = O((log n)^k)
> sqrt = O(sqrt n)
> lin = O(n)
> linlog = O(n * log n)
> linplog = O(n * (log n)^k)
> poly = O(n^k)
> exp = O(2^n)
> 
> Ordering:
> 
> Terms above are in increasing order.
> 
> Summation:
> 
> x + y = max(x, y)
> 
> Product:
> 
>        | 1       log      plog     sqrt  lin      linlog   poly  exp
> 
> -------+------------------------------------------------------------
> 1      | 1       log      plog     sqrt  lin      linlog   poly  exp
> 
> log    | log     plog     plog     ?     linlog   ?        poly  exp
> plog   | plog    plog     plog     ?     linplog  linplog  poly  exp
> sqrt   | sqrt    ?        ?        lin   poly     poly     poly  exp
> lin    | lin     linlog   linplog  poly  poly     poly     poly  exp
> linlog | linlog  linplog  linplog  poly  poly     poly     poly  exp
> poly   | poly    poly     poly     poly  poly     poly     poly  exp
> exp    | exp     exp      exp      exp   exp      exp      exp   exp
> 
> I've left a few question marks for the tricky cases. Ideas?
[...]

sqrt really belongs under poly, as far as asymptotic behaviour is
concerned. Basically, O(n^j) * O(n^k) for any real j, k > 0 is
asymptotically equal to O(n^(j+k)). Furthermore, O(O(n^j)^k) =
O(n^(j*k)). So you can treat polynomial complexities as a field of real
numbers, where + on the O(...) terms behaves like max(), * behaves like
+, and function composition behaves like ^.

Then exp behaves like an "infinite real", where exp > O(n^k) for all
real k>0. Its inverse, log, therefore, behaves like an "infinitesimal",
where O((log n)^k) for all real k>0 is less than O(n^k) for all real
k>0. (Yes, even O(n^(1/1000000)) will eventually outgrow O(log n).)

The log powers behave like "intermediate infinitesimals", where you have
O((log n)^j) < O((log n)^k) for all positive real j < k.

So these O-terms behave approximately like real numbers (poly) enhanced
with infinite quantities (exp and its derivations) and infinitesimal
quantities (log and its derivations), they follow the usual laws of
arithmetic. Therefore,

	O(n^k) * O(log n)

can be treated as the equivalent of a real number k + an infinitesimal
L, such that k < (k+L) < k+j for all real j>0. In other words,

	O(n) < O(n * log n) < O(n^(1+k))  for all k>0.

(Yes, even O(n^1.00000000001) will eventually outgrow O(n*log n). O(log
n) behaves like an infinitesimal.)

The nice thing about this is that you can simplify a lot of complicated
O(...) expressions just by applying algebra as described above on the
analogous {real + infinities + infinitesimals} system. Ordering
relations are preserved (for the most part -- this only breaks down with
pathological cases like O(sin n) which is unlikely to be ever
encountered). Also, function composition between poly and non-poly
complexities will generally be non-commutative, and mostly will break
the + = max analogy. (But it seems unlikely, in real-world algorithms,
to ever need to worry about the intricacies of exponential-time
algorithms, since generally they are to be avoided where possible.)

So you can get a (mostly) closed algebra just by mapping poly to the
real numbers, and then adding:

	L = infinitesimal quantity corresponding to O(log n)
	E = infinite quantity corresponding to exp

Various operations inside O(...) are thus mapped:

	+ inside O(...) = max(...)
	* inside O(...) = + between mapped quantities
	O(f(g(n))) = O(f(n)) * O(g(n))
	O(1) = 0

Example: is O(n^3*log(n)) better than O(n^2*(log(n))^3)?
Answer:
	O(n^3*log(n)) maps to 3 + L, and O(n^2*(log(n))^3) maps to 2 +
	L^3. Since L^3 is infinitesimal, (2 + L^3) is very close to 2,
	whereas (3 + L) lies slightly above 3. Therefore O(n^3*log(n))
	is definitely faster-growing than O(n^2*(log(n))^3).

This algebra leads to various interesting questions like:

- Is there an intermediate complexity that lies between poly and exp?
  Yes: since exp is mapped to the infinite quantity E, it follows that
  E/2 is still an infinite quantity (even though it's strictly less than
  E). E/2 corresponds to E*1/2, which is the composition of exp with
  sqrt, so it follows that O(n^k) < O(e^sqrt(n)) < O(e^n) for all real
  k>0. (There are, of course, many other possibilities.)

- Similarly, the log powers O((log n)^k) are *always* slower-growing
  than any polynomial complexity, because L*k, being still
  infinitesimal, will always < j for all real j>0. So even
  O((log n)^10000) will not outgrow O(n^1.000000001). Multiplying with a
  poly function preserves this relationship:

  	O(n^j * (log n)^k) --> j + L*k < j + m, for all real j,m>0, so
	O(n^j * (log n)^k) < O(n^(j+m)) for all j,m>0.

  Basically you're just displacing the mapped values by a constant.


T

-- 
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird. -- D. Knuth