5
$\begingroup$

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size of the input as opposed to the input itself (particularly in the case of numeric algorithms).

For instance, trial division for integer factorization takes up to $\sqrt N$ divisions to factor the integer $N$. However, the size of the input is the number of bits, $w = \lg(N)$. Thus, integer factorization takes $\mathcal{O}\left(2^{w/2}\right)$ time with respect to the size of the input ($w$ bits).

My question: Given the above, would it be considered correct to write in a CS article (relatively informal--on the scale of a blog post) to write that "integer factorization takes $\mathcal{O}(\sqrt{N})$ time with respect to the input variable $N$," and assume that the reader realizes they should substitute $w=\lg(N)$ to obtain the time complexity with respect to the size of the input?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
6
$\begingroup$

You have it backwards, but you are on to an important distinction.

$O(N)$ if $N$ is a number in the input is perfectly well-defined and can appear in, say, the $\Theta$-asymptotic of a runtime function.

In your example, note that $\sqrt{N} = 2^{w/2}$ and thus $O(\sqrt{N}) = O(2^{w/2})$ -- it's just another way of expressing the same function class, given the identity $w = \lg N$.

The distinction between $f(N)$ and $f(\langle N \rangle)$ is only important in the context of complexity classes. Many of those are defined along the lines of

Class $X$ contains all problems for which there is an algorithm with runtime in $O(f(|x|))$ where $x$ is an input string.

For examples, see pseudo-polynomial problems/algorithms.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you very much! Just to confirm: I have it backwards because people don't typically care about the size of $N$ unless they are talking about complexity classes? (I want to make sure exactly what I have backwards. ;)) And, also to confirm, you're using $\langle N\rangle$ to denote the size of $N$? (I haven't seen those symbols before.) $\endgroup$
    – apnorton
    Jul 19, 2014 at 23:40
  • $\begingroup$ (I'm marking this as accepted because it does answer my question and I don't want to forget to mark it as such. That said, I'd still like to know the answers to the clarifications I requested above. :) Thank you very much for your answer.) $\endgroup$
    – apnorton
    Jul 20, 2014 at 3:14
  • 3
    $\begingroup$ @anorton: I said you have it backwards because you implied one variant (of writing the same thing) was illegal because it can lead to confusion in some places. It's legal and correct; it's just that some people get the definition of "polynomial runtime" wrong (which may lead some people to advice against using the encoded numbers in runtime bounds, which again may lead some people to think it's illegal). $\endgroup$
    – Raphael ♦
    Jul 20, 2014 at 13:42
  • $\begingroup$ @anorton Yes, $\langle x \rangle$ is typically used to denote a "suitable" encoding of $x$. If $x$ is a number, usually some representation of logarithmic length is assumed (binary, ternary, ... but not unary). The size would be $|\langle x \rangle | = \lceil \log_b x \rceil$. $\endgroup$
    – Raphael ♦
    Jul 20, 2014 at 13:43
  • $\begingroup$ Ok, thanks! That answers all my questions! :) $\endgroup$
    – apnorton
    Jul 20, 2014 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.