1
$\begingroup$

So Fibonacci heaps can perform insertions in amortized constant time, and I came up with a sequence of heap data structures $H_k$ such that insertions can be performed in amortized $O((\log n)^{1/k})$ time where $n$ is the size of the heap. If we didn't know insertions could be performed in constant time, then my result would suggest it, since we can get arbitrarily close to constant running time asymptotics with my solution.

This led to me to wonder, is there an example of a family of algorithms or data structure operations, that are all functionally equivalent, and can be performed in $O(f_k(n))$ time, where $f_k$ is a sequence of functions such that $\lim_{k \to \infty} f_k(n) = 0$ for all $n$, but no constant time alogorithm/data structure operation can be found? Or at least where no constant time solution is currently known? I suspect the answer is yes but probably hard to prove. It would be very surprising if the existence of such family of algorithms with $O(f_k(n))$ running time would imply a constant time algorithm exists.

$\endgroup$

2 Answers 2

2
$\begingroup$

You can sort numbers in $O(\frac{n\log n}{k})$ for all fixed $k$, and $\lim_{k\to\infty} \frac{n\log n}{k} = 0$ for all fixed $n$.

$\endgroup$
2
  • 1
    $\begingroup$ OK I'm glad you posted this because it indicates some problem in my formulation, but trivially we could state that the running time of an algorithm that runs in $O(f(n))$ time is $O(f(n)/k)$ time for fixed $k$ and then take the limit of $f(n)/k$ as $k \to \infty$ for fixed $n$. So I need to figure out how to remedy this. Can you suggest a way around, using my example of heaps as a motivator? $\endgroup$ Commented Oct 19, 2015 at 14:28
  • 1
    $\begingroup$ You need a more uniform definition of big O that will still allow some non-trivial examples. Try to construct one and verify that it is non-trivial --- doesn't always hold, but does hold in some non-trivial cases. $\endgroup$ Commented Oct 19, 2015 at 14:30
2
$\begingroup$

There's a somewhat similar problem involving multiplication of $n$-bit numbers. Toom-Cook multiplication is a family of algorithms that (ignoring some minor details) do multiplication in time $O(n^{f_k})$, where $f_k = (\log(2k-1))/\log k$. We have $\lim_{k\to\infty}f_k=1$ but there is no known way to multiply in time $O(n)$. (In fact, the fastest known multiplication algorithms don't quite attain $O(n\log n)$ time.)

$\endgroup$

Your Answer

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

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