Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S$ be a set of numbers in $\mathbb N$.

Let us define two functions:

i) SumLessThan10 that returns 1, if the sum of the elements of $S$ is 9 or fewer and 0, if the sum is greater than 10.

ii) Mean that calculates the arthimetic mean of $S$.

Let us assume we have some iteration for calculating the sum and the mean (is there another way of doing it?), then for

i) SumLessThan10, as soon as the sum reaches 10 (if it does), we can finish the calculation; we don't need to necessarily iterate through the whole set of $S$.

ii) In order to calculate the mean, we must iterate through the whole set of $S$, we cannot use 'lazy-evaluation'.

Is there a name for functions that can (always/ sometimes) be lazily-evaluated in this way, to distinguish them from functions that must be run over all elements in a set in order to get the result?

share|improve this question
add comment

1 Answer 1

This does not fully answer your question but take a look at the query complexity/decision tree complexity of a function.

We start with a function $f:\{0,1\}^n \to \{0,1\}$ and ask how many queries do we need to make to calculate the function.

For example, query 1: what is the first bit (0 or 1) of the input?

Query 2: if the answer to query 1 is 0, what is the second bit of the input $\textit{but}$ if the answer to query 1 is 1, we instead ask what is the third bit of the input?

And so on until we have enough information to calculate the value of the function.

How is this related to your question?

Suppose you have a subset $S \subseteq \{1,\dots,n\}$. We can then specify this subset by a string of n bits, where the $i^{th}$ bit is $1$ if $i \in S$ and $0$ otherwise. So if $n=7$, the subset $S =\{1,4,5,7\}$ would correspond to the bitstring $1001101$.

Now your function SumLessThan10 takes the value 1 if the answer is yes and 0 if the answer is no. Your function SumLessThan10 has lower query complexity than some other functions because we don't have to make a full $n$ queries to calculate it; we can stop once we know enough information.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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