<p>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:</p>

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

<p>In Cryptography and strictly related fields, you can not assume that arbitrary precision arithmetic operations can be performed in constant time; so adding two <em>n</em> 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.</p>

<p>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. </p>

<p>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$.</p>

<p>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! </p>

CC BY-SA 3.0
2012-02-03T19:45:40.793Z
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
CC BY-SA 3.0
2012-02-03T20:12:40.970Z
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
CC BY-SA 3.0
2012-02-03T20:18:14.090Z
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
CC BY-SA 3.0
2012-02-03T20:20:53.013Z
So, continuing our discussion, you have an algorithm that is not linear in the size of its input: it depends on the magnitude of a number. Such an algorithm is called a pseudo-polynomial time algorithm.
Massimo Cafaro
CC BY-SA 3.0
2012-02-03T20:23:44.270Z
Finally, my sentence on the "target application" simply means that whenever you need to do arbitrary precision arithmetic, a uniform cost model will not give you a correct complexity analysis, and you need to resort to the other model.
Massimo Cafaro
CC BY-SA 3.0
2012-02-03T20:24:56.940Z
@vzn Sorry, I barely know any C, and no Java at all. What I can't understand are arguments such as "in this context we are dealing with small inputs, so we can use the uniform cost model". Dealing with arbitrarily large inputs is the whole point of asymptotics!
Emilio Ferrucci
CC BY-SA 3.0
2012-02-03T20:42:26.363Z
@unforgiven Thanks, things definetly make more sense now. One last thing: I have studied the Quicksort algorithm, which has $O(n \log(n))$ complexity in the average case. However this is done, as you said, by using unary encoding of the length n of the vector we want to sort. If we encoded it in bits we would have $O(n \exp(n))$. So what convention establishes that we use unary encoding of the input in this case?
Emilio Ferrucci
CC BY-SA 3.0
2012-02-03T20:59:56.197Z
@unforgiven Also (last question!), can you explain to me why there is a theoretical distinction between arbitrary and fixed precision arithmetic? I can understand how this distinction makes sense in practical implementations, but in theory, when we are dealing with asymptodic expressions, the size of the input is arbitrarily large. If we bound all possible inputs with a constant there isn't much analysis to do on algorithms! And thank you very much for your help and patience.
Emilio Ferrucci
CC BY-SA 3.0
2012-02-03T19:34:48.293Z
2012-02-03T19:34:48.293Z
Massimo Cafaro
<p>The definition of, e.g., <a href="http://en.wikipedia.org/wiki/P_%28complexity%29">class P</a> is unambiguous.</p>

<hr>

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

<ol>
<li><p>What is a single time step? This depends on the model of computation.</p></li>
<li><p>What is $n$? This depends on the problem.</p></li>
</ol>

<p>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."</p>

<hr>

<p>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 <a href="http://en.wikipedia.org/wiki/Random_access_machine">RAM model</a> 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.</p>

<p>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$.</p>

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

CC BY-SA 3.0
2012-02-04T00:20:01.657Z
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
CC BY-SA 3.0
2012-02-04T00:24:10.450Z
... 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
CC BY-SA 3.0
2012-02-04T00:35:01.803Z
@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
CC BY-SA 3.0
2012-02-04T00:41:06.850Z
@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
CC BY-SA 3.0
2012-02-04T00:44:00.853Z
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
CC BY-SA 3.0
2012-02-04T00:45:20.743Z
Ok, I just saw your last comment! Thanks a lot for clearing this up for me.
Emilio Ferrucci
CC BY-SA 3.0
2012-02-04T00:04:26.970Z
2012-02-04T00:04:26.970Z
Jukka Suomela
<p>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.</p>

<p>lets focus on sorting. the lower bound on sorting <em>operations</em> is proven to be $O(n \lg(n))$ where $n$ is the <em>number of elements</em> in the list eg see this <a href="http://en.wikipedia.org/wiki/Comparison_sort#Lower_bound_for_the_average_number_of_comparisons" rel="nofollow">wiki page, lower bound on sort comparisons</a>. now technically you are correct, if we then say the algorithm runs in the same time, this does not <em>seem</em> to count time to compare each element or <em>apparently</em> assumes $O(1)$ comparison time for all comparisons ie the <em>uniform cost</em> model.</p>

<p>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 <em>logarithmic cost model</em> that you mention, ie cost per each memory unit access (ie where comparing two longer elements takes time proportional to their size).</p>

<p>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$.</p>

<p>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 </p>

<p>$m \lg(m/ w)$ total steps. </p>

<p>but note that expression is simply $O(m \lg(m))$! so we have proven that <em>in either case</em> 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.</p>

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

CC BY-SA 3.0
2012-02-04T17:29:16.047Z
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
CC BY-SA 3.0
2012-02-04T17:42:42.573Z
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
CC BY-SA 3.0
2012-02-04T22:10:16.293Z
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ε
CC BY-SA 3.0
2012-02-05T00:59:23.957Z
plz forgive me! **upper bound**
vzn
CC BY-SA 3.0
2012-02-05T02:11:54.960Z
emilio-- the point is that Big-oh notation is very "resilient" against various quibbles about data representations in bits, bytes, or whatever. its also often resilient against the distinction of uniform vs logarithmic cost models. it even allows us to blur some of the accounting such that if the sort algorithm takes n lg(n) _comparisons_ then it runs in O(n lg(n)) steps/time without worring about details of worst case pairwise comparisons etcetera. but big Oh also has "gotchas". I wish I knew a good web page to emphasize all this. arguably it might make a good faq or blog post for this site.
vzn
CC BY-SA 3.0
2012-02-05T09:45:02.237Z
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ε
CC BY-SA 3.0
2012-02-05T13:24:22.203Z
@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 http://math.stackexchange.com/questions/86076/what-are-the-rules-for-equals-signs-with-big-o-and-little-o
Emilio Ferrucci
CC BY-SA 3.0
2012-02-05T19:32:53.120Z
yes E exactly nice find that would be an example of some "gotchas", & the way the notation is pushed etc & there are other examples
vzn
CC BY-SA 3.0
2012-02-04T02:30:02.387Z
2012-02-04T02:30:02.387Z
vzn
<p>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</p>

<ol>
<li><p>Difference between the <a href="http://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models" rel="noreferrer">uniform and logarithmic cost models</a>: this can, for example, make a difference, when evaluating the time complexity of something like <br/> 
<code>for i = 1, 2, ..., n do c(i)</code>,
where <code>c(i)</code> is an instruction such that the number of bits involved depends on <code>i</code>. <br/> 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. </p></li>
<li><p>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$.</p></li>
</ol>

<p>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? <br/> </p>

CC BY-SA 3.0
2012-02-03T20:02:52.950Z
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
CC BY-SA 3.0
2012-02-03T20:16:55.673Z
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
CC BY-SA 3.0
2012-02-03T20:25:12.663Z
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
CC BY-SA 3.0
2012-02-03T20:36:04.753Z
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
CC BY-SA 3.0
2012-02-05T02:17:02.190Z
try this page [big oh notation/wikipedia](http://en.wikipedia.org/wiki/Big_O_notation) maybe should be in cstheory faq
vzn
CC BY-SA 3.0
2012-02-05T13:03:40.037Z
...yes, thanks; I'm a third year math student and I'm pretty sure I have my calculus right. My question was basically on how to justify the differences in the definitions of complexity; not on asymptotic notations.
Emilio Ferrucci
<cc.complexity-theory><soft-question><time-complexity>
Different definitions of complexity
Emilio Ferrucci
# Different definitions of complexity

(Asked by: username_0 on 2012-02-03)

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](http://en.wikipedia.org/wiki/Analysis_of_algorithms#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?

**Tags:** cc.complexity-theory, soft-question, time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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"?  
> **username_1**: 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.  
> **username_0**: 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))$  
> **username_1**: try this page [big oh notation/wikipedia](http://en.wikipedia.org/wiki/Big_O_notation) maybe should be in cstheory faq  
> **username_0**: ...yes, thanks; I'm a third year math student and I'm pretty sure I have my calculus right. My question was basically on how to justify the differences in the definitions of complexity; not on asymptotic notations.  

---

## 3 answers

### Answer by username_2 on 2012-02-03. Score: 5 | Accepted answer

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!

> **Comments:**
> **username_0**: 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."  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_2**: So, continuing our discussion, you have an algorithm that is not linear in the size of its input: it depends on the magnitude of a number. Such an algorithm is called a pseudo-polynomial time algorithm.  
> **username_2**: Finally, my sentence on the "target application" simply means that whenever you need to do arbitrary precision arithmetic, a uniform cost model will not give you a correct complexity analysis, and you need to resort to the other model.  
> **username_0**: @vzn Sorry, I barely know any C, and no Java at all. What I can't understand are arguments such as "in this context we are dealing with small inputs, so we can use the uniform cost model". Dealing with arbitrarily large inputs is the whole point of asymptotics!  
> **username_0**: @unforgiven Thanks, things definetly make more sense now. One last thing: I have studied the Quicksort algorithm, which has $O(n \log(n))$ complexity in the average case. However this is done, as you said, by using unary encoding of the length n of the vector we want to sort. If we encoded it in bits we would have $O(n \exp(n))$. So what convention establishes that we use unary encoding of the input in this case?  
> **username_0**: @unforgiven Also (last question!), can you explain to me why there is a theoretical distinction between arbitrary and fixed precision arithmetic? I can understand how this distinction makes sense in practical implementations, but in theory, when we are dealing with asymptodic expressions, the size of the input is arbitrarily large. If we bound all possible inputs with a constant there isn't much analysis to do on algorithms! And thank you very much for your help and patience.  

---

### Answer by username_3 on 2012-02-04. Score: 10

The definition of, e.g., [class P](http://en.wikipedia.org/wiki/P_%28complexity%29) 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](http://en.wikipedia.org/wiki/Random_access_machine) 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?").

> **Comments:**
> **username_0**: 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...)  
> **username_0**: ... 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?  
> **username_3**: @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".  
> **username_3**: @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.  
> **username_0**: 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.  
> **username_0**: Ok, I just saw your last comment! Thanks a lot for clearing this up for me.  

---

### Answer by username_1 on 2012-02-04. Score: -1

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](http://en.wikipedia.org/wiki/Comparison_sort#Lower_bound_for_the_average_number_of_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).

> **Comments:**
> **username_0**: 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).  
> **username_1**: 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.  
> **username_4**: 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.  
> **username_1**: plz forgive me! **upper bound**  
> **username_1**: emilio-- the point is that Big-oh notation is very "resilient" against various quibbles about data representations in bits, bytes, or whatever. its also often resilient against the distinction of uniform vs logarithmic cost models. it even allows us to blur some of the accounting such that if the sort algorithm takes n lg(n) _comparisons_ then it runs in O(n lg(n)) steps/time without worring about details of worst case pairwise comparisons etcetera. but big Oh also has "gotchas". I wish I knew a good web page to emphasize all this. arguably it might make a good faq or blog post for this site.  
> **username_4**: 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.  
> **username_0**: @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 http://math.stackexchange.com/questions/86076/what-are-the-rules-for-equals-signs-with-big-o-and-little-o  
> **username_1**: yes E exactly nice find that would be an example of some "gotchas", & the way the notation is pushed etc & there are other examples  

---

