Folk Complexity Theory

There's one kind of posts on this blog that get the most hostile reactions. It's not politics (nobody reads those), flaming programming languages, or computer games - the most controversial subject is Big O analysis! Here are relevant posts:

• Modern x86 assembly
  
• Big O analysis considered harmful
  
• Practical O(n) problem impossible to solve even for n=1

Basically I claim that Big O is useless in most practical situations. And I get flamed a lot. At first I tried to explain to the flamers how they are mistaken, then I basically ignored them after explanations proven to be pointless, but now I see that it's all just big misunderstanding. What I call Big O analysis is a fairly precise construct of computer science. But that's not how most people use the Big O notation - they follow Folk Complexity Theory, which I want to describe here.

The Official Complexity Theory

First, here's a brief repetition of Algorithms and Data Structures 201, or whatever your course explaining this was.

An algorithm is O(f(n)) if in a particular model of computations, if there exist some constants n₀, and c, such that for all input lengths greater than n, computation time is less than c × f(n). A problem is O(f(n)) if in particular model of computations there exists a O(f(n)) algorithm that solves it.

Models of computations are things like different varieties of Random access machine, and different models usually only differ by some logarithmic factors. Sometimes you want to assume that adding two numbers takes constant time, sometimes that it takes time proportional to logarithm of their sum, and details like that. If you disregard logarithmic factors, you don't have to be all that precise about which variety of RAM you're using. That's about it.

In particular, if the problem is only defined for constant-sized input, then by definition it has complexity O(1). There exists some c, such that for all possible sizes, running time of the algorithm is less that c × 1.

So breaking AES-128 is O(1). As is breaking RSA-4096. Breaking RSA-n for arbitrary n isn't, but that's entirely unrelated problem. Breaking AES-n is meaningless concept, as AES isn't defined for arbitrary n.

In particular classes like P, and NP, don't depend much on what reasonable computation model you're using. They're defined on Deterministic Turing Machines for reference (which is polynomial factor slower than RAM), but if something is P on DTM, it's P on RAM and vice versa.

How cryptography handles it

As I got a lot of flames about my claim that breaking RSA-4096 is O(1), let me explain how cryptography handles it. So cryptography doesn't use Big O notation much.

Security is measured in bits - a cryptosystem has k bits of security if the attacker must perform 2^k times as many operations as legitimate user to defeat security of the cipher. For some types of security key size and security are related - for block ciphers security = key size, for hash collisions security = key size/2. For public key cryptography these bit measures can be only approximately specified in terms of key size, and whatever formula we have we're completely uninterested in its asymptotic form, as all feasible key sizes are small, and constant factors are of great interest to us.

The Folk Complexity Theory

And now the main subject of the post - The Folk Complexity Theory. When people say some algorithm is O(f(n)), they actually mean that for "normal" sizes of inputs, on actual computers, it's expected running time is between two "small" constants times f(n) times reasonable number of log(n) factors as long as they don't push the constant too high.

• O is used sort of like Θ of the official theory. Folk O(n) algorithm is not considered to be O(n²).
  
• So bubble sort is O(n²), as number of operation tends to be something like 10n². Logarithmic factor for addressing and arithmetic is not considered at all.
  
• Merge sort is O(n×log(n)), as number of operation tends to be something like 10n×log(n). Notice how log factor for number of operations is included here as it's significantly higher than allowed small constants; but log factor for cost of addressing and arithmetic is not, as on normal computers it's constant up to 2³², which is very big n. And only doubles for 2⁶⁴, which is too ridiculously high n to bother. Exactly the same reasoning can be used for both log factors, so this is highly peculiar.
  
• Quick sort is O(n×log(n)), the Folk Complexity Theory always deals with typical case, not worst case.
  
• Breaking AES-128 is O(2ⁿ) because the constant is too big to be allowed. It doesn't matter that there's no n here, and AES is not defined for other key sizes. The problem must be reformulated to have n, no matter if it makes any sense or not. Number of operation like 2¹⁴⁰ is simply "not allowed", while 2¹²×2ⁿ is.
• Breaking RSA-4096 is likewise O(2ⁿ), even though there's no n here at all.
  
• Forging signature of n-byte message signed with RSA-4096 is, uhm... O(2ⁿ). Wait, n is already something else... O(2^k) then maybe? The problem is reformulated as RSA-k because large constants are not allowed, and usually there's no point saying O(2^k+n), as n is too small to matter for all practical n.
• As an added bonus "NP" usually means Θ(2ⁿ), for real or imagined n. This is spectacularly incorrect (most problems are not decision problems; there can be no Θ bounds even for NP-complete problems until NP != P is proven, and every P problem is NP), but doesn't cause much confusion in practice.
  

This is the source of all confusion - I was talking about the Official Complexity Theory, while most Redditors interpreted it as Folk Complexity Theory statements, in which they were obviously untrue.

Is Folk Complexity Theory useful?

It's quite amusing that so many people flame me for saying the Official Complexity Theory is overrated, and don't even know it. But I'm not going to blame them - who needs it once they're past exams anyway? In practice Folk Complexity Theory is actually better heuristic than the Official kind. We program real computers. On real input sizes. ceil(log₂(n)) factors shouldn't be ignored, but ceil(log_4294967296(n)) factors which represent cost of arithmetic and addressing on most 32-bit computers hardware totally can and should. And so should all log(log(n)), which nobody ever bother with past exams.

The Folk Complexity Theory has weird status - it's neither mathematics like the Official theory, nor practice like actual benchmarking. It's just a bunch of heuristics dressed as something much more formal than they are. Often even fairly useful heuristics. Just nothing more than that, and not worth the flames.