5
$\begingroup$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?

$\endgroup$
12
$\begingroup$

Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) \in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) \leq c\frac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, since $f$ maps to $\mathbb{N}$. In my understanding, even an algorithm that immediately terminates, takes at least $1$ step (namely to terminate), i.e., $\forall n\colon f(n)\ge 1$. So no such algorithm can exist.

$\endgroup$
  • $\begingroup$ It might also make sense to explain here why does $f$ map to $\mathbb{N}$. $\endgroup$ – svick Sep 10 '12 at 16:21
  • 3
    $\begingroup$ It depends somewhat on your model. e.g. in some models we only care about the number of comparisons, or external memory reads, or bandwidth, or rounds of communication, etc. Depending on the model, some operations might not "count" and it would be possible to get $f(n) = 0$. $\endgroup$ – Joe Sep 10 '12 at 18:18
2
$\begingroup$

Bucket sort's insertion sort step is O(1/n) on average.

Reference - CLRS Section 8.4

BUCKET-SORT(A)
1 n ← length[A]
2 for i ← 1 to n
3     do insert A[i ] into list B[nA[i ]]
4 for i ← 0 to n − 1
5     do sort list B[i ] with insertion sort
6 concatenate the lists B[0], B[1], . . . , B[n − 1] together in order

$T(n) = \theta(n) + \sum_{i=0}^{n−1} O(n_{i}^{2})$

Taking expectations of both sides and using linearity of expectation, we have

$E[T(n)] = \theta(n) + \sum_{i=0}^{n−1} O(E[n_{i}^{2}])$

It is proved that $E[n_{i}^{2}] = 2 − 1/n$

Hence step 5 takes $2 - 1/n$ time. Overall complexity of bucket sort is

$\theta(n) + n\cdot O(2 − 1/n) = \theta(n)$.

$\endgroup$
  • 2
    $\begingroup$ Given @Peter's answer above, that doesn't sound right... $\endgroup$ – Joe Sep 10 '12 at 18:15
  • 5
    $\begingroup$ This example is not O(1/n), it's O(1) (or 2 to be exact). This is both according to the analysis above, where you say 2-1/n (each time step 5 is run) which is not O(1/n), and intuitively, sorting a bucket which has O(1) expected elements will take O(1) expected time. That said, creating a substep of an algorithm that runs in O(1/n) time on average is fairly straightforward. The "substep" is critical because generally you can't read the value of $n$ in $1/n$ time; you need to be in a framework where the algorithm already knows the value of $n$ it needs to act on. $\endgroup$ – SamM Sep 10 '12 at 19:32
  • 4
    $\begingroup$ (cont) Imagine a randomized algorithm that calls an $O(1)$ subroutine with probability 1/n. This subroutine takes a total of $O(1/n)$ average time per element. Obviously, this does not really answer the question in the affirmative (which makes sense because the answer is "no"; if an algorithm runs in $O(1/n)$ time it doesn't have time to read the input so it doesn't "know" to go faster; this is similar to Peter's argument). But it does give a case where this can happen. This sort of analysis is used in data structures (i.e. amortized rotation cost) so it's not as contrived as it may seem. $\endgroup$ – SamM Sep 10 '12 at 19:37
  • 2
    $\begingroup$ I checked the corresponding section (9.4) in the second edition, and the book does not say anything about running time being O(1/n). Therefore, unless the authors introduced an error in the third edition, it is your interpretation that is incorrect. $\endgroup$ – Tsuyoshi Ito Sep 11 '12 at 17:32
  • 2
    $\begingroup$ @Ankush: Heresy!! Everyone knows The Art of Computer Programming is the One True Scripture! (But even Knuth makes mistakes.) $\endgroup$ – JeffE Sep 11 '12 at 21:31
2
$\begingroup$

By definition, all functions (even the trivial) must perform at least 1 operation. It is impossible to perform half of a step; computers are discrete machines, and work incrementally. As such, the complexity $\Omega(1)$ is the lower time bound of all computational operations. In addition, for any operation accepting any N inputs, it must deal with at least a constant number of them at once (even if that number is zero). It's impossible to start at using one unit of space and halve that space infinitely; at some point your algorithm will reach the atomic unit of space for the computation (one bit, one electron, one string, whatever) and from that point you will use either zero or one of those atomic units, thus arriving at a constant base case. Thus, $\Omega(1)$ is also the lower space bound of all algorithms.

Now, it is possible, trivial even, for an algorithm to produce an output on that order of magnitude or cardinality. Given N elements, you can return 1/N of them (array[x] produces an output 1/N the size of the input array). But, this takes constant time (calculate the location of the element by offsetting the address of the array by the number and size of its elements, and return the bits beginning at that offset and continuing for sizeof(elementType)).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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