4 ms·
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
by w8rbt 7y ago
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).
- Sharlin 7y agoIn 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.
- w8rbt 7y agoRight, it's a pity RSA does not use 32 or 64 bit ints.
- BubRoss 7y agoWhat does that have to do with anything? The original thread was about performance guarantees of API functions.
- rightbyte 7y agoIt'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.
- enedil 7y agoNo, 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.
- w8rbt 7y agoWhat's the runtime of 75^4096 mod 236?
- jerf 7y agoThat sounds like a problem that is not described by "Standard 32-bit or 64-bit multiplication as implemented in hardware".
- nwallin 7y agoa^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://godbolt.org/z/KNX4pi https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...
- brucedawson 7y agoO(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.
- joppy 7y agoI 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 https://gmplib.org/manual/Multiplication-Algorithms.html