I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements.

Is there a software metric that describes "data growth" for an algorithm or do I simply write "the data grows exponentially"?

btw: The size of the $2^n$ elements varies , so I cannot determine their size (storage)

  • $\begingroup$ So for $n$ elements as input you have $2^n$ elements in the result set, each of varying size? $\endgroup$
    – dkaeae
    Apr 8 '19 at 8:52
  • $\begingroup$ yes, does this metric have a name? or do i have to describe it like this? $\endgroup$
    – pony2deer
    Apr 8 '19 at 10:06

Apparently, the best you can do is write something on the lines of "the number of result sets is exponential in the number of input input elements". This is better than simply saying "the data grows exponentially" since such growth must happen with respect to some quantity. It also might be a good idea to state the value $2^n$ somewhere (in the more technical sections) so it is clear it is a precise and not an asymptotic estimate.

It is unfortunate you cannot estimate the size of each result set. Are you sure not even very conservative or even empirical estimates are possible? (If that is the case, then consider adding at least one of those.)


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.