This is the new meaning of "went up exponentially", meaning just "a lot". The algorithm is O(n-cubed) for n = the number of switches, and O(m-squared) or so for m = the number of ports per switch, so O(n-cubed times m-squared), rather than O(2 to the n power).

(Can you tell that I don't trust the forum software on this site to handle asterisks correctly? And by "correctly" I mean, of course, "the way I want".)

You sure about that? I think it's perhaps worse than (truly) exponential. Because of the nesting it feels like a permutation of combinations (or vice-versa) or maybe even a combination of permutations of combinations. It's building an array of all ports on an array of all switches but one for an array of every switch on the network and there appears to be no check on whether a given path has already been checked from the opposite side.

It's so awful I may be misunderstanding due to a fail-safe in my brain preventing me from comprehending how truly disgusting it is.

int portCounter = 0;
int macCounter = 0;
for each port {
ports[portCounter] = port;
portIndexes[portCounter] = macCounter;
for each MAC on port {
allMACs[macCounter++] = MAC;
}
}

Shouldn't portCounter be being incremented somewhere in there?

It's still to a fixed power though; if m=n then it's n^5, while if m=n^2 it's n^7. It gets pretty bad, but ultimately any fixed power isn't as bad as truly exponential.

I am reminded about a memory test I wrote for a microprocessor. It did all sorts of bit tests and addressing tests, and soon grew into factorial space when counting the iterations. I realized after attempting to run the thing, and looking at the progress after a minute or two that it MIGHT finish in a couple of years time to complete the test. I pared it down to a few simplified tests that while functional, weren't as exhaustive in their scope.

I think it's factorial not fixed power. On a hypothetical network, if you change from 8-port switches to 16-port it's not building arrays with twice the additional members, nor just 2 to the 8th power additional members, but because of the recursion I think it has to have 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 = 518918400 additional members, on top of the 8! it already would've had to do. I think.

And the recursion, I think in this pseudo code, is recursed? So that factorial is multiplied by the number of switches, factorial. Minus one for not counting the current switch.

Exponential growth means M^N where N is the varying value e.g. 2^2; 2^3; 2^4; ... It's the opposite of logarithmic growth, and is truly horrendous.

Raising to a non-varying positive power N^M e.g. 2^2; 3^2; 4^2 is bad (especially as M increases) and for small values of N can be worse than exponential growth, but in the long run is not as bad as exponential growth.

This is a really clear explanation, thanks. I've often thought business people were technically wrong when they talk about "exponential" growth when they mean vaguely non-linear, but I've forgotten most of my high school maths and never bothered to re-acquaint with exponential, geometric, polynomial, etc.

Any algorithm that has a finite upper bound runs in constant time. O(1). Even if that bound relies on the maximum array size for a language raised to an absurd value.

int startIndex;
int endIndex;
for (int ictr = 0; ictr < ports.length;="" ictr++)="" {="" if="" (ports[ictr]="=" port)="" {="" startindex="portIndexes[ictr];" endindex="portIndexes[ictr" +="" 1];="" }="" }="">

So, on the last iteration through the loop, we reference a non-existent member, The correct limit (portCounter) is out of scope (or in some other scope), depending upon how this particular Verkakt language works.

Less than (endIndex - 1)? So we arbitrarily drop the last mac address for every single port. If a port has only one mac address, we return an array with nothing resembling a mac address.

I wonder how efficient it would be if it actually was playing with a full deck, and not so many invalid values.

Of course, "exponential growth" really just means anything that doesn't scale well. n log n might be tolerable, because if you can really assess an algorithm is n log n, you've probably made it perform as well as you can. Polynomial or worse usually won't fly unless you can restrict the problem space.

Addendum 2017-01-11 23:16:
Your formatting kung fu is better than mine. <bow/>

This is still fine. I just found something obfuscated in my project's codebase which is O(n^n) that just got reduced to O((log(n))^n), because it is too messy, crap and live, I could not allocate time for rewriting the entire module.

I once had the joy of rewriting a permission management system built by someone who liked linear searches. He'd do linear searches on sorted arrays after bubble sorting them. I suppose at least he understood the code he'd written. And his code worked really well on the test dataset, where he had 3 or 4 users in 2 groups who could be granted 2 or 3 different permissions on 5 or 6 objects in a very simple tree. It was pretty flawless and all his snazzy treeviews and smart navigation was pretty snappy.

Then we pointed it at the real system, with a few thousand users, 20 or so permissions ("can view but not modify data owned by my group") and thousands of objects in a fairly deep hierarchy. Somehow the very first screen, with all the trees closed down to a single top node, didn't load. Well, one core of the CPU went to 100% and we waited. And waited. After lunch we waited some more. Eventually we decided it didn't work.

I was given the rewrite and a three week deadline. Not just for the user interface, but for "the other bit" as well... using that permission tree to decide what data to display to a given user, and which bits they could modify.

Looking at thee source code I gave up counting the O(N) complexity after about 30. To draw a single permission in the "permissions this user has" tree, he'd linear search the array of permissions for each object, carefully recursing through the tree of objects to find out what permissions it inherited from objects above it, every time. Then he'd look for the next un-drawn permission, using a linear search through the already-drawn objects to see if each permission in the master list had been drawn yet. I cried.

I made it work, basically by not doing iterations except where I had to, like linking tree nodes to their parent object directly and a few other tricks.

Admin

Cannot recist to be frist

Admin

Frist is no better than sicint

Admin

This is the new meaning of "went up exponentially", meaning just "a lot". The algorithm is O(n-cubed) for n = the number of switches, and O(m-squared) or so for m = the number of ports per switch, so O(n-cubed times m-squared), rather than O(2 to the n power).

(Can you tell that I don't trust the forum software on this site to handle asterisks correctly? And by "correctly" I mean, of course, "the way I want".)

Admin

You sure about that? I think it's perhaps worse than (truly) exponential. Because of the nesting it feels like a permutation of combinations (or vice-versa) or maybe even a combination of permutations of combinations. It's building an array of all ports on an array of all switches but one for an array of every switch on the network and there appears to be no check on whether a given path has already been checked from the opposite side.

It's so awful I may be misunderstanding due to a fail-safe in my brain preventing me from comprehending how truly disgusting it is.

Admin

Shouldn't

`portCounter`

be being incremented somewhere in there?Admin

It's still to a fixed power though; if m=n then it's n^5, while if m=n^2 it's n^7. It gets pretty bad, but ultimately any fixed power isn't as bad as truly exponential.

Admin

I am reminded about a memory test I wrote for a microprocessor. It did all sorts of bit tests and addressing tests, and soon grew into factorial space when counting the iterations. I realized after attempting to run the thing, and looking at the progress after a minute or two that it MIGHT finish in a couple of years time to complete the test. I pared it down to a few simplified tests that while functional, weren't as exhaustive in their scope.

Lesson learned!

Admin

Y'all should be grateful it used iteration rather than recursion!

Admin

I think it's factorial not fixed power. On a hypothetical network, if you change from 8-port switches to 16-port it's not building arrays with twice the additional members, nor just 2 to the 8th power additional members, but because of the recursion I think it has to have 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 = 518918400 additional members, on top of the 8! it already would've had to do. I think.

And the recursion, I think in this pseudo code, is recursed? So that factorial is multiplied by the number of switches, factorial. Minus one for not counting the current switch.

Admin

Or am I failing to read the example correctly...?

Admin

But since power and exponent are synonyms I think exponential is appropriate when raising to any power, even if it's a constant power.

Admin

Exponential growth means M^N where N is the varying value e.g. 2^2; 2^3; 2^4; ... It's the opposite of logarithmic growth, and is truly horrendous.

Raising to a non-varying positive power N^M e.g. 2^2; 3^2; 4^2 is bad (especially as M increases) and for small values of N can be worse than exponential growth, but in the long run is not as bad as exponential growth.

Admin

So if exponential growth is where the power increases, what is it called when the base increases? It's not linear, pretty sure not geometric.

Admin

Polynomial time, of course. Here https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time

Admin

I think i once owned a set of Psuedo.

Admin

It looks to me as a simplified Traveling Salesman problem (not wigthed) . Would then mean O(n!)

Admin

Don't step on my Blue Psuedo Shoes

Admin

This is a really clear explanation, thanks. I've often thought business people were technically wrong when they talk about "exponential" growth when they mean vaguely non-linear, but I've forgotten most of my high school maths and never bothered to re-acquaint with exponential, geometric, polynomial, etc.

Admin

Any algorithm that has a finite upper bound runs in constant time. O(1). Even if that bound relies on the maximum array size for a language raised to an absurd value.

Admin

The future of the field...

Admin

Is "Array[]" an array of integers or an array of arrays? Or is this R?

Admin

Oh, this treasure trove of WTF just keeps going

So, on the last iteration through the loop, we reference a non-existent member, The correct limit (portCounter) is out of scope (or in some other scope), depending upon how this particular Verkakt language works.

Less than (endIndex - 1)? So we arbitrarily drop the last mac address for every single port. If a port has only one mac address, we return an array with nothing resembling a mac address.

I wonder how efficient it would be if it actually was playing with a full deck, and not so many invalid values.

Of course, "exponential growth" really just means anything that doesn't scale well. n log n might be tolerable, because if you can really assess an algorithm is n log n, you've probably made it perform as well as you can. Polynomial or worse usually won't fly unless you can restrict the problem space.

Addendum 2017-01-11 23:16:Your formatting kung fu is better than mine. <bow/>Admin

Interesting use of formatting there...

Admin

This is still fine. I just found something obfuscated in my project's codebase which is O(n^n) that just got reduced to O((log(n))^n), because it is too messy, crap and live, I could not allocate time for rewriting the entire module.

Admin

I once had the joy of rewriting a permission management system built by someone who liked linear searches. He'd do linear searches on sorted arrays after bubble sorting them. I suppose at least he understood the code he'd written. And his code worked really well on the test dataset, where he had 3 or 4 users in 2 groups who could be granted 2 or 3 different permissions on 5 or 6 objects in a very simple tree. It was pretty flawless and all his snazzy treeviews and smart navigation was pretty snappy.

Then we pointed it at the real system, with a few thousand users, 20 or so permissions ("can view but not modify data owned by my group") and thousands of objects in a fairly deep hierarchy. Somehow the very first screen, with all the trees closed down to a single top node, didn't load. Well, one core of the CPU went to 100% and we waited. And waited. After lunch we waited some more. Eventually we decided it didn't work.

I was given the rewrite and a three week deadline. Not just for the user interface, but for "the other bit" as well... using that permission tree to decide what data to display to a given user, and which bits they could modify.

Looking at thee source code I gave up counting the O(N) complexity after about 30. To draw a single permission in the "permissions this user has" tree, he'd linear search the array of permissions for each object, carefully recursing through the tree of objects to find out what permissions it inherited from objects above it, every time. Then he'd look for the next un-drawn permission, using a linear search through the already-drawn objects to see if each permission in the master list had been drawn yet. I cried.

I made it work, basically by not doing iterations except where I had to, like linking tree nodes to their parent object directly and a few other tricks.

Admin

Be careful with that much Pseudo -- Cross any major borders and you'll be doing hard time