Re:A DoS Attack Against the C# Compiler
by Aloraman on Wednesday November 08, 2017 @07:59PM
(#15658769)
Well, if you variate generic arity N, you are going to get N^3 which is exponential.
If you variate nest level M, you are indeed going to get 6 ^ N which is 'just' polynomial.
However, if you just look upon the code sample, in most case it is assumed that both N and M are variated, and if both of them are growing with same limiting behavior, then there is O(N^N) complexity. This complexity is even worse than factorial!
[ Parent
| on HN ]
Re:A DoS Attack Against the C# Compiler
by unwind on Thursday November 09, 2017 @03:48AM
(#15660843)
Uh it's been ... rather long since my last exposure to formal CS, but did you drop some 'M's?
Re:A DoS Attack Against the C# Compiler
by Aloraman on Thursday November 09, 2017 @05:44PM
(#15666406)
Oh crap... yeah. I meant O(N^3) and O(6^M). If both are varied - O(N^M), if both are increasing with same order of magnitude, then complexity can be written as O(N^N) which is O(N! * e^N / sqrt(N))