0
$\begingroup$

Suppose that you have a huge (terabytes worth) collection of numbers, and you know that you will, in a future, need to run some statistics of it. In order to cut future work, you notice that, by pre-computing some key statistics, you can make other statistics be computable in sub-linear time. For example, if you store the sum and the length of the collection, you can, in a future, compute the average in linear time. If you also store the variance, you can compute the standard deviation. You can keep adding specific statistics in hope to cover as many "future computations" as you could.

My question is: is there any way to prepare the dataset such that any arbitrary linear-time function could, in a future, be processed in sub-linear time? In other words, is the snippet below possible?

# builds an ideal pre-computation of an arbitrary bit string
precomputed = precompute(arbitrary_bit_string)

# builds a circuit for a "countOnes" function
# could be any other arbitrary linear-time function
countOnes = buildCircuit("... an String->Int algorithm here ...")

# computes the number of ones in sub-linear time
average = execute(precomputed, countOnes)
$\endgroup$

1 Answer 1

1
$\begingroup$

Multiplying the size of the dataset you have to pre-calculate over does not increase the amount of time it takes to calculate the average when the sum and length are pre-calculated; it will be a constant time operation. Moreover, calculating the sum and length of a dataset in itself is only linear time (doubling the dataset will result in doubling the amount of time it takes to pass over all data and therefore is only linear, the 'addition' operation is constant-time and does not contribute to the time complexity).

However, I think what you meant is the following:

If I had any possible data readily accessible, would that mean I can run a more optimal algorithm over this new dataset than I could over the original dataset?

The answer is no.

Some examples:

  • The original dataset contains 10 integers. We want to calculate the total when we multiply each number by every other number. This is an O(n^2) algorithm since for each element we have to pass over all other elements. If we had precalculated the set resulting from multiplying each number by all other numbers it would only take linear time; O(n) since we only have to sum the numbers in the dataset. So for this function the hypothesis holds.

  • The original dataset contains 10 integers. We want to calculate the sum of the first two numbers. This will take O(1) time, as the size of the dataset does not increase the time it takes to sum the first two numbers. Now assume that we had precalculated this value then it would still be an O(1) algorithm. After all, no (0) time is still considered constant time.

  • The original dataset contains 10 integers. We want to know the value at the first index. This is obviously a constant time O(1) function and, as a result, one that cannot be done more efficiently regardless of any precalculated data.

P.S. do note that this is only the purest sense that it does not hold for every function; it might very well be that every real-world application can more efficiently be run over a set containing pre-calculated data).

$\endgroup$
4
  • $\begingroup$ Not sure I get what you mean by talking about quadratic algorithms... I'm asking if you could prepare for a linear-time function, not a quadratic one... i.e., precomputed = prepare(dataset); average = run(averageCircuit, precomputed), where run would execute in sub-linear time for any linear-time circuit. $\endgroup$
    – MaiaVictor
    Jan 18, 2017 at 20:26
  • $\begingroup$ Only if the 'sub-linear' function itself does not require a pass over an amount of data that grows with the dataset (as it implies). Say your algorithm calculates and prints the average of every 50 entries (0-49, 50-99...) then the expected output is a list of averages. Even if you precalculate these averages, the algorithm that returns them will have to loop over the n/50 entries in the precalculated dataset, which is still linear. $\endgroup$
    – DeBunkeD
    Jan 18, 2017 at 21:02
  • $\begingroup$ What is we restrict ourselves to decision algorithms? String -> Bool functions? :) $\endgroup$
    – MaiaVictor
    Jan 18, 2017 at 21:10
  • $\begingroup$ If you allow the precalculated data to be anything, then obviously every linear-time algorithm's solution can be found in constant time by simply having the precomputed dataset be or contain the exact answer to the algorithm. $\endgroup$
    – DeBunkeD
    Jan 18, 2017 at 21:20

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.