3 ms·
Looking at the "decompiled" version, it's clearly cubic, not exponential. There are 6 type arguments to the outer instantiation of 'Class' in the field declara
by ScottBurson 9y ago
Looking at the "decompiled" version, it's clearly cubic, not exponential. There are 6 type arguments to the outer instantiation of 'Class' in the field declaration; each of those arguments is itself an instantiation of 'Class' with 6 type arguments, each of which is a third level of instantiation of 'Class' with 6 type variable references, for a total of 216 (= 6^3) type variable references.
There's nothing exponential going on here. Note that in the expression 6^3, the number that's varying is the 6, not the 3. If it were the other way around, that would be exponential.
I realize "exponential" has come into common use meaning just "growing very fast", and it's sometimes pedantic to insist on a distinction between polynomial growth and exponential growth, but in a discussion of algorithmic time complexity, we should get it right!
- tomcam 9y agoThis was exponentially better than the other comments
- matthewwarren 9y agoWell played ;-) (I love a good pun!!)
- al2o3cr 9y agoThe "levels" that are being changed are the number of nested `Inner`s - the decompiled example is Inner.Inner inner ("Level 2" in the article's terms) but the crashing one is Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner inner Your calculation of the variable references is correct, but the thing the article's experiment varies is the exponent.
- ScottBurson 9y agoAh, I see — it's cubic in the number of type parameters, but it's exponential in the depth of the type reference in the field declaration. My bad; I didn't read carefully enough.
- Aloraman 9y agoWell, 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!
- unwind 9y agoUh it's been ... rather long since my last exposure to formal CS, but did you drop some 'M's?
- Aloraman 9y agoOh 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))