4 ms·
> However, I still haven’t found any studies which show what this relationship is like. Does the number of bugs grow linearly with code size? Sub-linearly? Supe
by dustingetz 15y ago
> However, I still haven’t found any studies which show what this relationship is like. Does the number of bugs grow linearly with code size? Sub-linearly? Super-linearly? My gut feeling still says “sub-linear”.
interesting, my gut says exponential, which is why cost and likelihood of project cancellation shoot up in the largest projects.
edit: i have been corrected below, i concur with quadratic.
- baddox 15y agoAre you sure you mean exponential? I think quadratic is a more reasonable guess.
- blahedo 15y agoHe might be using "exponential" to mean "superlinear", which seems to be the sense a lot of my students try to use it in (as well as non-technical people).
- baddox 15y agoNow that you mention it, I guess non-technical people do tend to use that definition. I had never thought about it before. It's unfortunate, considering there's a big difference between, say, quadratic and exponential growth. In fact, it tends to be a more impactful difference than between linear and quadratic, especially regarding algorithms.
- voodoomagicman 15y agoI am not aware of the difference. Is it that exponential means something like c^n, superlinear is n^c, and linear cn?
- Locke1689 15y agoSuperlinear is anything above linear. This includes pseudolinear (e.g., O(nlog n)). Exponential is O(m^n). Linear is O(n). Edit: And polynomial is O(n^m).
- baddox 15y agoWhat Locke1689 said. If you're not familiar with big O notation, linear is like f(x) = 2x, quadratic is like f(x) = x^2, and exponential is like f(x) = 2^x. There's a huge difference between quadratic and exponential: exponential grows significantly faster as x increases. For computing, the difference is significant. Cobham's thesis says that polynomial algorithms (which includes quadratic) are reasonable to perform, while exponential algorithms aren't.
- dustingetz 15y agowithout straining my brain, to me its reasonable to measure complexity by number of interacting components, which is a combination, which is geometric, which is a discrete exponential, right?
- sage_joch 15y agoThe number of edges in a complete graph is n*(n - 1)/2, so by that metric it would be quadratic.
- lurker19 15y agoYes but the number of nodes is n, and an "interaction" among m nodes might not be decomposable to a chain of pairwise interactions, which raises the ceiling back to exponetial (actually factorial, which is worse).
- scarmig 15y agoWhat corresponds to interactions that aren't decomposable as pairwise interactions? Race conditions? Resource utilization? Real bugs (and the nastier ones), but probably a minority. So factorial with a relatively small constant in front of it. But obviously the real answer is to write a program that will correctly verify all other programs.
- joshhart 15y agoIt can be quadratic. Think about drawing all possible lines between points (possible components in software): Make a table with columns being # points and the # lines you can draw between them. 1 0 2 1 3 3 (triangle) 4 6 (box with a criss cross) 5 10 (5 point star, with everything connected) ... This relation is n * (n - 1) / 2
- lurker19 15y agoYes, combination, which is factorial, which is yet larger than exponential. Not sure what you mean by "geometric" in this context.
- deleted 15y ago[deleted]
- MattJ100 15y agoThe Art of Unix Programming by esr covers just this question[1]. Nowadays module/file size is one of the most important factors in how I design and write my code. [1]: http://catb.org/~esr/writings/taoup/html/ch04s01.html http://catb.org/~esr/writings/taoup/html/ch04s01.html