# Different definitions of complexity

I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes me as odd is that the definitions I have encountered so far seem to differ greatly. In particular, the differences that I have noted are

1. Difference between the uniform and logarithmic cost models: this can, for example, make a difference, when evaluating the time complexity of something like
for i = 1, 2, ..., n do c(i), where c(i) is an instruction such that the number of bits involved depends on i.
When dealing with, say, sorting algorithms, all references I have ever come across adopt the uniform cost model, while in Cryptography, the time complexity of algorithms is always calculated in terms of bit operations.

2. Another difference is the definition of the size of an input: again, in sorting algorithms, the size of the input is simply the length of the vector that has to be sorted (as in graph searching algorithms, the number of nodes and edges). In Cryptography and Computational Number Theory, instead, the size of the input is always the number of bits involved. I don't know if this distinction is considered part of 1. , but it certainly makes a huge difference, since an algorithm that is linear using the first criterion, becomes exponential when adopting the second. Factorizing integers would be linear (actually, $O(\log{n} \sqrt{n})$) if we considered the input size of $n$ to be $n$.

One could justify these discrepancies with arguments such as "well, in Number Theory we are dealing with large integers, so adopting a more realistic model makes more sense". But this defies the whole purpose of evaluating asymptotic expressions for the complexity of algorithms! If, in certain contexts, we knew that all inputs were smaller then a fixed quantity, then everything would be $O(1)$. Also, how can it be possible to define, without ambiguity, complexity classes and other rigorous Computer Science concepts, when the definition of complexity varies from field to field?

• do not fully understand the question however there is an interesting old paper that factoring is in P in the sense that if arithmetic operations on large integers have constant (uniform) cost. I found the paper after deriving the result myself & wondering if it had been published. but its been 20 years since I found it, dont recall the authors. which does nicely demonstrate how important it is to get the "cost model" correct. – vzn Feb 3 '12 at 20:02
• Sorry if the question isn't well formulated: What I meant to ask was: we have different cost models and different criteria to evaluate the size of an input. So how can we rigorously define notions that depend on complexity, such as complexity classes? Nobody in their right mind would consider factorization to be $\in P$: however, given the right cost model, you can make it that way! So what is a rigorous definition of "getting the cost model right"? – Emilio Ferrucci Feb 3 '12 at 20:16
• factoring in P is an open question. frankly Im not really that familiar with any papers in CS that use the uniform cost model, none come to mind as far as I know. is it more common in number theory? do you have an example of it? it is true that over there in number theory they tend to have different ideas of "complexity". also from what I can tell the difference between uniform vs logarithmic is only a logarithmic factor and much of complexity theory (not all) is concerned with much greater separations than logarithmic ie it doesnt matter in many contexts eg most major class separations. – vzn Feb 3 '12 at 20:25
• Yes, what I meant is that factoring isn't certainly considered to be a polynomial time algorithm yet, that is with already existing algorithms (the best algorithm for factoring is the Number Field Sieve). But by switching models even the most trivial algorithm for factoring (i.e, check all the factors up to $\sqrt{n}$, divide, and start over with the quotient) has complexity smaller than $O(\sqrt{n} \log(n))$ – Emilio Ferrucci Feb 3 '12 at 20:36
• try this page big oh notation/wikipedia maybe should be in cstheory faq – vzn Feb 5 '12 at 2:17

The performances of an algorithm are always analyzed in the context of a well defined computational model. Traditional sequential models, e.g. the RAM model, assume that:

• All memory accesses are equally expensive;
• There are no concurrent operations;
• All reasonable instructions take unit time;
• With the notable exception of function calls!
• Constant word size;
• Unless we are explicitly manipulating bits!

In Cryptography and strictly related fields, you can not assume that arbitrary precision arithmetic operations can be performed in constant time; so adding two n bits numbers requires $O(n)$ instead of $O(1)$, multiplying them requires $O(n \lg n)$ using the Fast Fourier Transform (there are better algorithms) etc.

In practice, using the uniform or the logarithmic cost model strictly depends on the target application. Even using the uniform cost model, please consider carefully what the "size of the input" actually is. Here you must remember that the efficiency of solving a problem strictly depends on how you encode the problem.

As an example, consider a simple algorithm requiring as input just an integer $x$, and whose complexity is $O(x)$. For instance, think about a loop that is executed $x$ times, and in each iteration of the loop you perform an operation requiring $O(1)$. So, you conclude that the algorithm is linear in $x$.

However, if you encode the input $x$ using the traditional binary representation of the integer $x$, then the input length is $n = \lfloor \log x \rfloor +1$. Therefore, the running time of the algorithm is $O(x) = O(2^n)$, which is exponential in the size of the input!

• Thanks for your answer, you have made several interesting observations. My question, however, is: how can these differences be put aside when defining, say complexity classes? Take, for example, the observation in your last paragraph: it seems as though this makes the definition of $P$ to be completely ambiguous. How is this not so? Also, I would be very interested if you could expand on the sentence : "In practice, using the uniform or the logarithmic cost model strictly depends on the target application." – Emilio Ferrucci Feb 3 '12 at 19:45
• uniform cost eg for arithmetic operations manipulating most #s is a reasonable empirical approximation if one is not dealing with large #s (in other words, more useful in an applied context) but basically complexity theory class separations are not defined in terms of uniform cost. to understand this concept in an applied context, try comparing cost of operations on "native" number types vs BigDecimals in Java. the former are reasonably approximated as uniform cost & the latter are not. – vzn Feb 3 '12 at 20:12
• A complexity class, say P, is still well defined under the assumption of a reasonable encoding. For instance, it does not matter if you encode the input using a ternary encoding instead of a binary encoding etc. The only problem you may experience is strictly tied to the use of a unary encoding. Let's use again the same example algorithm with input x. If the integer x is provided in unary —a string of x 1s— then the running time of the algorithm is O(n) on length-n inputs, which is polynomial time! This is why you may be fooled to think that factoring is linear. – Massimo Cafaro Feb 3 '12 at 20:18
• @Emilo: None, the convention is that we use the size of the input, which is the number of objects to be sorted. (The algorithm then sorts them using unit-cost access to a comparator oracle.) – user6973 Feb 3 '12 at 22:34
• @unforgiven: multiplying 2 n-bit numbers requires $O\left(n\cdot \operatorname{log}(n)\cdot 2^{O(\operatorname{log}^*(n))}\right)$ time. $\hspace{.3 in}$ – user6973 Feb 4 '12 at 1:22

The definition of, e.g., class P is unambiguous.

However, what is ambiguous is something like "the running time is $O(n)$". As you have observed, there are two sources of ambiguity:

1. What is a single time step? This depends on the model of computation.

2. What is $n$? This depends on the problem.

To make it completely unambiguous, you would state something like "the running time in the RAM model is $O(n)$, where $n$ is the number nodes."

Usually, we can afford to be a bit sloppy. The model is often clear from the context; in the case of algorithms, it is usually the RAM model unless otherwise specified. Moreover, there are various conventions regarding the definition of $n$. For example, in the context of graph algorithms, $n$ almost always denotes the number of nodes (and $m$ is the number of edges) – these are just conventions that you have to learn.

If you are really interested in logarithmic factors, then you have to be careful with these details. The same algorithm might be $\Theta(n)$ or $\Theta(n \log n)$ or $\Theta(n/\log n)$ if you slightly vary your model of computation or your definition of $n$.

However, if something like "polynomial time" is good enough for you, then you can ignore most of these details. Typical models of computation can simulate each other with a polynomial overhead (time $x$ in one is at most time $\mathrm{poly}(x)$ in the other), and typically an input can be encoded in $\mathrm{poly}(n)$ bits, no matter what happened to be your precise definition of $n$. For example, an $n$-node graph can be encoded as a string of $n^2$ bits. Hence you can usually say "runs in polynomial time" without worrying too much about the details ("polynomial in what?", "polynomial number of what?").

• Thank you for your answer. I had read that complexity classes such as $P$ are "robust" under changes of computation model (Turing Machine, RAM, RASP...); what was bothering me is that, as you said, changing the definition of the size of an input critically alters the time complexity. This doesn't only change the complexity up to polynomial transformations, since exponential algorithms become polynomial ones! To make the definition of complexity classes unambiguous one would need to make the size of an input, an integral part of the definition of algorithm: (cont...) – Emilio Ferrucci Feb 4 '12 at 0:20
• ... by this I mean, an algorithm for, say, factoring, where a certain criterion for the evaluating the size of the input is used, is defined to be a different algorithm from that obtained by using a different criterion to evaluate the input size, but the same instructions. Is this the correct way to avoid ambiguity? In this case, it still strikes me as odd that there isn't a unique, or at least preferential way to calculate input sizes. Why aren't bits used to calculate the input size of a graph which we want to search, or of a vector the components of which we want to sort? – Emilio Ferrucci Feb 4 '12 at 0:24
• @Emilio: Regarding non-polynomial transformations: Yes, we could come up with a strange definition of $n$. For example, we could study graph algorithms and define $n = 2^x$, where $x$ is the number of nodes, and then advertise that our algorithm has running time that is "polynomial in $n$". Similarly, we could require a strange inefficient encoding of our input and then advertise that the the running time is "polynomial in the size of the input". But why would we do this; just to confuse people? In practice, you will encounter various reasonable definitions of "$n$" or "input size". – Jukka Suomela Feb 4 '12 at 0:35
• @Emilio: "Why aren't bits used": One reason is simply convenience – it's convenient to use natural parameters (and also natural units in the running time). Another reason is that you actually get more information if you can have multiple parameters. Consider, for example, a graph algorithm with a running time $O(n^{3/2} + m)$ – this gives a much better idea of the running time than any upper bound of the form $f(x)$, where $x$ is the number of bits in an encoding. – Jukka Suomela Feb 4 '12 at 0:41
• Sure, if you put it that way we could define $n$ to be anything we want! I haven't taken a serious course in theoretical computer science yet so I don't know, but it would seem reasonable that a standard way to calculate input sizes existed (i.e. one that doesn't depend on the problem, or the programmer's advertising). For example, if everything were implemented in Turing machines, would there really be any ambiguity as to what $n$ is? It seems really strange that, the way definitions stand, I can wake up one morning and say factoring is in $P$! Thank you very much for your help. – Emilio Ferrucci Feb 4 '12 at 0:44

Ill take a stab at answering part of this [where I think you have a valid point] although I think parts of the question relates to a basic misunderstanding of Big-Oh notation which others are helping address in the comments.

lets focus on sorting. the lower bound on sorting operations is proven to be $O(n \lg(n))$ where $n$ is the number of elements in the list eg see this wiki page, lower bound on sort comparisons. now technically you are correct, if we then say the algorithm runs in the same time, this does not seem to count time to compare each element or apparently assumes $O(1)$ comparison time for all comparisons ie the uniform cost model.

so then lets take into account the real time it takes to compare each element. this might seem counterintuitive but think about it like this. now determine runtime by the logarithmic cost model that you mention, ie cost per each memory unit access (ie where comparing two longer elements takes time proportional to their size).

consider the total size of the input (elements times size of each element) as $m$ and the "width" of each element as $w$ in terms of "memory units" (say chars, digits, bytes, turing tape squares etc). then simply $n \cdot w = m$.

consider in best case a pairwise comparison between two elements does not need to examine all $w$ units of each element, but in worse case (exercise-- devise inputs that force this) each comparison will compare close to $w$ units. so then the algorithm takes comparisons times steps per comparison $n \lg(n) \cdot w$ total steps in worst case. but look at that! by simple algebra thats equal to

$m \lg(m/ w)$ total steps.

but note that expression is simply $O(m \lg(m))$! so we have proven that in either case even when we take into account time per comparison, we get the same answer! this is because theres an inherent "hidden" tradeoff between max number of comparisons and size of each element. this invisible tradeoff is so common in all problems that its almost never explicitly stated or accounted.

ps I dont think Ive seen the above argument in any textbook but I formulated it when I was a CS beginner pondering over the apparent/seeming gaps, handwaving, or inconsistencies in the theory like you are (and by the way, still think they may exist, but not in this case).

• Thanks for your answer. I am not the downvoter, but there are a few things I didn't get here. First of all you can't just substitute $\frac{m}{w}$ and get rid of the $w$ as if it were a constant, because (if I understand correcly what it is), it isn't a constant. As mentioned by an answer there are two possible ambiguities: the definition of input size, and cost model. If you change the input size to the number of memory units (which as I understand, your $nw = m$ is), you will have to look at a precise definition of memory unit (for example, with bits, take logarithms). – Emilio Ferrucci Feb 4 '12 at 17:29
• the point is that O(n) notation is inherently "worst case" & what removes the necessity of strict accounting. by defn m/w < m and therefore the substitution is correct based on defn of O(n). exercise for reader: suppose that every element to sort has different lengths & apply logarithmic cost model. – vzn Feb 4 '12 at 17:42
• No, no, no. Big-Oh notation and its ilk have nothing whatsoever to do with "worst-case", or running times, or even algorithms. O(f(n)) is shorthand for "at most c f(n) for some constant c" and nothing else. – Jeffε Feb 4 '12 at 22:10
• No, you're still missing the point. Big-Oh notation is "resilient" against quibbles about the model of computation because it has nothing to do with the model of computation. Big-Oh notation does not have any "gotchas"; it's just an inequality with a hidden constant. It's just notation. – Jeffε Feb 5 '12 at 9:45
• @vzn The rigorous interpretation of the big O notation is $O(f(n)) = \{g: \mathbb{N} \to \mathbb{R} \ |\ \exists M \in \mathbb{R}: g(n) \leq Mf(n) \}$. This is why it shold be referred to as a set (i.e. $g \in O(f)$); the notation is often abused by writing stuff like $f(n) = g(n) + l(n)O(f(n))$ (because it works!); here is a very interesting related question math.stackexchange.com/questions/86076/… – Emilio Ferrucci Feb 5 '12 at 13:24