News for hackers. Stuff that matters.

A comment on O(N^2) in CreateProcess.

Re:O(N^2) in CreateProcess by w8rbt on Monday April 22, 2019 @07:33AM (#19718061)
O(n^2) is polynomial and perfectly acceptable for many use cases. Basic multiplication is O(n^2), as are many other operations.

    for i = 1 -> n:
        for j = 1 -> n:
            do something
Although, if the outside n differs in size from the inside n, it should be written O(nm).
[ Parent | on HN ]
Re:O(N^2) in CreateProcess by joppy on Monday April 22, 2019 @10:41AM (#19719261)
I would argue that O(n^2) algorithms are really only acceptable if n is known to be bounded well ahead of time. In large integer libraries like GMP, O(n^2) multiplication is switched out for asymptotically better and better algorithms as n gets too large: https://gmplib.org/manual/Multiplication-Algorithms.html
[ Parent | on HN ]
Re:O(N^2) in CreateProcess by Sharlin on Monday April 22, 2019 @08:15AM (#19718277)
In this case it doesn't seem to be. Although admittedly executables as large as in the article are rare, process creation on Windows is slow enough as it is, without extra inefficiencies.

As an aside, basic multiplication is O(n^2) only if your number type is arbitrarily wide. Standard 32-bit or 64-bit multiplication as implemented in hardware is constant time.

[ Parent | on HN ]
Re:O(N^2) in CreateProcess by rightbyte on Monday April 22, 2019 @09:09AM (#19718596)
It's tautological to state that for a fixed number of nodes, mutliplication is constant time.

Off course it is. The n is fixed.

Also as a side note, n^2 is not the lowest order algorithm for multiplication.

[ Parent | on HN ]
Re:O(N^2) in CreateProcess by enedil on Monday April 22, 2019 @09:47AM (#19718868)
No, what is meant by that, is that multiplying 2 by 3 takes about the same time as multiplying 432434232 by 1213213213. Not only bounded time, about the same.
[ Parent | on HN ]
Re:O(N^2) in CreateProcess by w8rbt on Monday April 22, 2019 @09:57AM (#19718942)
What's the runtime of 75^4096 mod 236?
[ Parent | on HN ]
Re:O(N^2) in CreateProcess by jerf on Monday April 22, 2019 @12:23PM (#19720177)
That sounds like a problem that is not described by "Standard 32-bit or 64-bit multiplication as implemented in hardware".
[ Parent | on HN ]
Re:O(N^2) in CreateProcess by nwallin on Monday April 22, 2019 @02:50PM (#19721653)
a^n mod m requires O(log(n)) iterations in the outer loop. If m fits in one machine word, each iteration is O(1). If m is large, each iteration is O((log m)^2).

For the specific case of m = 236 and n = 4096, it requires 12 multiplication and 12 division operations. For n = 4095, I think it actually requires 22 multiplications and 22 divisions. Also, if m is a compile time constant, the divisions can be implemented as multiplications instead, which gives a constant factor speedup.

https://godbolt.org/z/KNX4pi

https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...

[ Parent | on HN ]
Re:O(N^2) in CreateProcess by brucedawson on Wednesday April 24, 2019 @10:15PM (#19744455)
O(1) - constant time. The answer is 29. I just happen to know that.

I think you need an 'n' in there before it is meaningful to ask about the runtime.

[ Parent | on HN ]
Re:O(N^2) in CreateProcess by w8rbt on Monday April 22, 2019 @08:25AM (#19718342)
Right, it's a pity RSA does not use 32 or 64 bit ints.
[ Parent | on HN ]
Re:O(N^2) in CreateProcess by BubRoss on Monday April 22, 2019 @02:23PM (#19721341)
What does that have to do with anything? The original thread was about performance guarantees of API functions.
[ Parent | on HN ]