0
$\begingroup$

Is it possible to calculate the average between n numbers in a static random access array of some size in less than $O(n)$ time? I know that the trivial approach is $O(n)$, but can I do it in less time using a data structure or a certain preparation? or both? I am asking for hints, not a solution.

Note: The array is of some length. What and I mean by between is when given 2 indexes a and b, I have to calculate the average of the sub array $[a+1,b-1]$. And I have to keep it updated while the data structure is managed, that's why I said it was a dynamic set, in other words a random access array. I do not know of any restrictions, just asking if it's possible in less than $O(n)$.

$\endgroup$

closed as unclear what you're asking by FrankW, David Richerby, Juho, D.W., Rick Decker Jun 2 '14 at 21:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Is the array of length n? what precisely do you mean by "between"? $\endgroup$ – d'alar'cop Jun 2 '14 at 13:26
  • 1
    $\begingroup$ What is $n$? The number of elements? Do you need to compute the average once or keep it updated while the data structure is managed? If the latter, is the running time restricted for a sngle run or for all of them combined? $\endgroup$ – FrankW Jun 2 '14 at 13:27
  • $\begingroup$ The array is of some length. What and I mean by between is when given 2 indexes a and b, I have to calculate the average of the sub array [a+1,b-1]. And I have to keep it updated while the data structure is managed, that's why I said it was a dynamic set, in other words a random access array. I do not know of any restrictions, just asking if it's possible in less than $O(n)$. $\endgroup$ – HaloKiller Jun 2 '14 at 13:31
  • $\begingroup$ So you keep the average updating as you add/remove elements?... the subindices stay the same? $\endgroup$ – d'alar'cop Jun 2 '14 at 13:36
  • 1
    $\begingroup$ @Trinarics You are only specifying your full question in the comments! Please explain your question in the question statement itself. The way it is currently stated, the average can be maintained in $O(1)$ time. $\endgroup$ – Yuval Filmus Jun 2 '14 at 15:20
4
$\begingroup$

I'll assume that you are computing the average of the elements of an array of fixed size and that you can change the value at some position at any moment. You want a data structure that supports the following two operations:

  1. Update element at location $i$,
  2. Query sum of elements in range [$i$, $j$].

A binary indexed tree (aka Fenwick tree) performs both in $\cal O(\lg n)$.

$\endgroup$
2
$\begingroup$

I am assuming that the query must be done in less than O(n) time and preprocessing can take any amount of time.

Pre-processing: Store the values in a Binary Tree like data structure.Every node of tree has sum of its subtree and number of children(To calculate average).So the base case is that you have n leaves having n values and we go leaves to root to construct this tree.You can do this pre-processing in O(nlogn) time.

Query: Now whenever you update a value you need to go to leaf along the path from top node to this leaf and the sum only changes in the nodes along this path so this takes only O(logn) time.

Correct me if I am wrong.

$\endgroup$
  • 1
    $\begingroup$ How do you compute the average for a subarray that does not align with a subtree? $\endgroup$ – FrankW Jun 2 '14 at 13:43
  • $\begingroup$ My approach cannot compute it,I assumed question asks average of n elements where n is given to you and n is the size of array $\endgroup$ – iLoveCamelCase Jun 2 '14 at 14:38
  • $\begingroup$ Also user mentioned update is O(1) so my method would be invalid anyway. $\endgroup$ – iLoveCamelCase Jun 2 '14 at 14:39
  • $\begingroup$ My method has same complexity as above answer $\endgroup$ – iLoveCamelCase Jun 2 '14 at 14:45

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