2
$\begingroup$

When looking through a few questions at StackOverflow¹ that all ask for algorithms to select k distinct random numbers out of N, I've become confused about how to compare the answers in terms of time and space complexity.

  • each algorithm has two parameters, N and k
  • and returns k elements

In terms of Big O notation, all the algorithms worth speaking of are O(N) overall.

But there are still major differences between them:

  • Some require ~k steps while others ~N
  • Some can return elements one by one while others only return them all at the end.
  • Most require all the k (or even N) elements to be present in memory at once, but some are able to return each one in sequence and discard it.

Now to unambiguously put these distinctions when describing each algorithm's complexity? More specifically, I'm interested in the standard way it is done in formal papers so as not to reinvent the wheel.


¹https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1/16097246, https://stackoverflow.com/questions/158716/how-do-you-efficiently-generate-a-list-of-k-non-repeating-integers-between-0-and-n, https://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, https://stackoverflow.com/questions/54059/efficiently-selecting-a-set-of-random-elements-from-a-linked-list

$\endgroup$
  • $\begingroup$ Landau notation is not useful here. While you can something like $O(k + n)$, nobody really knows what it means. $O(k)$ and $O(n)$ are different things, though; you can use those. The other two bullets are simply out of scope for runtime bounds. $\endgroup$ – Raphael Nov 14 '16 at 19:50
  • $\begingroup$ @Raphael, we know what $O(k+n)$ means when we're talking about a subset of the problem with some known relationship between the variables, e.g. $k < \log n$. I think that's the situation we have most of the time and that it's perfectly reasonable to talk about. $\endgroup$ – Karolis Juodelė Nov 14 '16 at 20:53
  • $\begingroup$ @Raphael I don't require the answers to be limited to Landau notation (note the absense of the corresponding tag) - or to just a single expression in it, for that matter. $\endgroup$ – ivan_pozdeev Nov 14 '16 at 22:50
2
+50
$\begingroup$

You can report:

  • The running time (e.g., $O(k)$ vs $O(n)$),

  • The space requirements (e.g., $O(1)$, $O(k)$, etc.), and

  • Whether the algorithm is a streaming (online) algorithm or a batch algorithm. A batch algorithm returns the entire answer at once. A streaming or online algorithm returns numbers one at a time. You might also be interested in the notion of "delay"; for instance, a $O(\log n)$ delay algorithm returns algorithms one at a time, taking at most $O(\log n)$ steps (running time) to output each number.

Since there are two variables here, $n$ and $k$, if you report a running time like $O(k)$, it may be helpful to mention explicitly that the constant is independent of $n$.

Formal papers aren't always as formal as you might think. They'll use standard notation and terminology where they exist, but if standard notions don't cover it, they'll just use the English language to describe the situation, or they may introduce some new terminology and provide a definition for it. That's the great thing about human language: it provides a way to express arbitrary new concepts, even ones we don't already have a pre-existing standard name for.

$\endgroup$
  • $\begingroup$ My primary concern is to avoid reinventing the (square) wheel. We programmers are very prone to this. So, you're telling me there's no wheel despite the concepts being around for more than half a century? $\endgroup$ – ivan_pozdeev Jan 19 '17 at 21:14
  • $\begingroup$ @ivan_pozdeev, maybe I just have a different perspective, but I interpret my answer as saying there is a wheel and describing the wheel. Maybe the message that is implicit in my answer is that you don't need special words/notions that are specific to this problem -- standard notions from algorithm analysis suffice. Or perhaps I have misunderstood what you are asking -- that's entirely possible, too. $\endgroup$ – D.W. Jan 19 '17 at 23:15
  • $\begingroup$ $O(n^0)$ looks like a concise way to say the space/time doesn't depend on $n$. $\endgroup$ – ivan_pozdeev Jan 20 '17 at 11:29

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.