2 ms·

Not necessarily. In fact it can get in the way because complexity theory ignores all those ugly little constant numbers. More important than complexity theory i

• jerf 12y ago
  "In fact it can get in the way because complexity theory ignores all those ugly little constant numbers." No, it doesn't. A given person may be, but the theory does not. It so happens that complexity theory makes heavy use of a mathematical construct, the "big-O notation", that makes it easy to ignore low-order term's impact on a process, but that is a tool it uses, not the totality of the theory. I assure you that if you walk up to a complexity theorists and say "Your ignoring of constant factors makes your entire discipline worthless!" you're more likely to get laughed at than blow their minds. You want to analyze the real impact of some algorithm in the face of having Big Ints and dealing with cache issues? Complexity theory is ready for you. I've seen it done. The equations get nastybig fast, but fortunately computer algebra systems can chew right them. Amusingly, in the end you end up doing something very similar to O() anyhow and just start semi-arbitrarily chopping off insignificant terms to figure out what's actually going on in the enormous expression. But this can still be a useful exercise to get a sense of where the low-order terms may be dominating, for how long, and whether there's anything useful to do about it.