Different definitions of complexity

Question

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?

Answer 1

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!

Answer 2

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?").

Answer 3

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).