story : complexity

the other day, a software component we use was r e a l l y slow.

it took us a while to even identify the culprit.

we contacted the developer, and after some back&forth, he said the problem was "quadratic".

this is comp sci geekspeak for it takes long, and the bigger the input is, the longer it takes -- in fact, the time required doesnt just increase as the input grows [this would be 'linear'] but actually, it grows more more as the input grows.

example:

if 1 input -- say one page of text -- takes 1 second to process, then you'd expect 2 inputs to take 2 seconds. This would be called linear.

but if the problem -- whatever's done in the processing -- is non-linear, then 2 pages might take, say, 4 seconds.

and 10 pages 100 seconds.

this would be called quadratic. (n pages take n² seconds).

welcome to the wonderful world of complexity theory!

we say

linear problems are in complexity class O(n)

quadratic problems are O(n²)

the general case of this is the class of polynomial problems, O(n^c), for some constant c

really really complex problems are exponential: ~~O(nⁿ)~~ O(cⁿ), for some constant c

so if the processing problem in the example above were exponential, 10 pages would take something like 10000000000 seconds, which is like 317 years or so. egads.

we were very impressed by his choice of words, but wondered how a simple urlencode problem could be quadratic.

well, to make a longer story shorter, it wasn't -- or isn't, as The Computer Scientist is wont to say. it wasn't the problem that was quadratic, just the implementation.

helpful pointer: that last sentence makes you chuckle, if you're a geek.

ergo, today's mantra, and let it be henceforth & always all our todays': We simply do not know yet the limits of disentanglement. We do not know yet whether intrinsic intricacy can be distinguished from accidental intricacy.

_______________________________________________________________
originally from 07:59:43 in K