1

How is computational complexity defined if the algorithm:

  • ...yields many results? As a total (then an algorithm producing a set of k cannot be faster than O(k) ) or per element (then the estimate must be multiplied to compare it with non-set-producing algorithms)?
    • What about storage complexity - does an estimate reflect if the entire set needs to be present in memory at once or each consecutive element can be produced and discarded?
  • ...has multiple parameters? A separate figure for each parameter or something combined?

An example that suits both cases is selecting k elements from N. E.g. is there a difference in the estimate depending on whether ~k or ~N steps are required?

I'd like to see some hard evidence: the formal definition of the term in these cases and/or how these ambiguities are eliminated in CS papers rather than just random thoughts and/or personal experience. The goal is to work out a complete, state-of-the-art solution to eliminate these ambiguities in my (and others') texts once and for all.

The questions that had me puzzled about this are: Unique (non-repeating) random numbers in O(1)?, How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N, Algorithm to select a single, random combination of values?, Efficiently selecting a set of random elements from a linked list.

Community
  • 1
  • 1
ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152
  • 1
    For the multiple parameters question, have a look at [Parameterized complexity or fixed-parameter tractability.](https://en.wikipedia.org/wiki/Parameterized_complexity) – sascha Sep 09 '16 at 23:21
  • Not having received any input of desired quality, I've now asked the "formal method" part [at cs.se](http://cs.stackexchange.com/questions/66046/eliminating-ambiguity-when-referring-to-complexity-in-cases-of-multiple-paramete), as formal things are more on-topic there. – ivan_pozdeev Nov 17 '16 at 08:01

2 Answers2

1

These questions are usually answered by context.

You are right that an algorithm takes at least O(k) time when returning k elements. At least if it returns the elements at once. If the algorithm is invoked multiple times to get the result one element at a time, the stated time complexity may relate to per-element time. Amortized Complexity may help in these cases. For example, the union-find data structure has an amortized time complexity of O(alpha(n)) per operation. Space complexity usually does not include the space to store the result. But again, this should be clear from context.

For multiple parameters (or other independent or dependent variables), complexities are usually stated in a single expression. E.g., querying interval trees requires O(n + m) time, where n is the number of elements in the tree and m is the number of returned elements. Other variables may include data distribution or other characteristics.

Nico Schertler
  • 32,049
  • 4
  • 39
  • 70
  • So, for the question "how CC is defined", you basically say there's _no definition?_ – ivan_pozdeev Sep 10 '16 at 00:31
  • No, there is a definition, of course. You just need to clarify which complexity you state. As mentioned, there are a few options. And sometimes, people are not very careful with terminology. So I wouldn't rely on some questions to get confused. – Nico Schertler Sep 10 '16 at 00:36
  • Okay, rephrasing: "there's no _official, agreed-upon_ definition". Of the grade useful for science papers, that is. And, you say _"You just need to clarify which complexity you state."_ but don't tell "which complexities" _there are_ - i.e. which are _typically_ used. As the linked questions show, it's _not_ clear from context, contrary to your claim. – ivan_pozdeev Sep 11 '16 at 15:35
  • 1
    It is very algorithm-specific. If your algorithm consists of a single function that you call once, it is quite clear. If the algorithm or data structure supports multiple function calls, you may want to consider amortized time complexity. In any case, you should state it in the form "the time for generating a single random number is ...", "the time for doing x k times is ..." and so on. If you do so, it is bullet-proof. Which of the linked questions is confusing you? – Nico Schertler Sep 11 '16 at 19:32
  • http://stackoverflow.com/questions/196017/ - O(1) is unattainable - how am I to speak about complexity with this in title?; http://stackoverflow.com/questions/158716/ - some algorithms require `~k` steps while others - `~N`; some need an array of `k`, others - of `N`; some are even capable of issuing elements one by one (whether they are accumulated into an internal array and returned together at the end is an implementation detail). It'd be very good if you demonstrate your reasoning on examples (e.g. take the "good" answers - those referencing CS papers). – ivan_pozdeev Sep 11 '16 at 20:30
  • The first one is not very clear, indeed. But since it is not possible to generate the list in O(1), the author must mean the time complexity to generate the next element. For the second one - the problem is generating the list (not just a single element). So if an algorithm requires a number of steps proportional to `k``, then it is `O(k)`. If the number of steps is proportional to `n`, then it is `O(n)`. – Nico Schertler Sep 11 '16 at 20:44
0

According to the answer at CS.SE:

  • Time complexity and space complexity shall be reported separately and separately for each variable: "O(k) and O(n) time, O(1) space".
    • If the time/space doesn't depend on some of the variables but not all, this can be told in plain text or with something like O(n0) for brevity (there's no universal convention here)
  • Whether all the results are returned at the end or one by one is reflected by refferring to the algorithm as streaming (online) (one by one) or batch (all at the end)
    • For a streaming algorithm, its delay can also be described:

      For instance, a O(log n) delay algorithm returns results one at a time, taking at most O(log n) steps (running time) to output each result.

ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152