 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best ofâ€¦
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
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(ncubed) for n = the number of switches, and O(msquared) or so for m = the number of ports per switch, so O(ncubed times msquared), 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 viceversa) 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 failsafe 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 8port switches to 16port 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 nonvarying 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 nonlinear, but I've forgotten most of my high school maths and never bothered to reacquaint 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 nonexistent 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 20170111 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 undrawn permission, using a linear search through the alreadydrawn 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
Admin
The article was an amazing one and it was truly delightful to go through it! I have to write my paper for me along the same lines and the article has been super helpful in the regard! Thanks a bunch and I am very happy to have learned about it.