# Computing exam averages in less than linear time

This is the question:

A spreadsheet keeps track of student scores on all the exams in a course. Each row of the spreadsheet corresponds to one student, and each column in a row corresponds to his/her score on one of the exams. There are r students and c exams, so the spreadsheet has r rows and c columns. Devise an algorithm to compute the exam averages for each student and the class average for each exam.

(It's from an ungraded practice problem set, not homework).

It seems fairly straightforward to me to do this in linear time($O(c*r)$), but I suspect there is a faster way to do it. Is there a reasonable way to do this with better O()?

My thoughts: At first I thought I could do this by storing the average values and updating them, but I don't think this would really satisfy the requirements of the problem: given just the exam scores, getting the averages would take at least as much time, if not more.

• Sequential or parallel? I'm guessing you can do it in $O(log c + log r)$ time on $O(c/log c + r/log r)$ CPUs, assuming that random access to a row, a column, a cell, and the size of a column or row is $O(1)$. – Jörg W Mittag Jun 6 '17 at 9:09
• @ Jörg W Mittag Can you expand on that? Would that mean the answer I accepted is incorrect? – Aperson123 Jun 6 '17 at 15:04
• @JörgWMittag Parallelizing the algorithm like this may change the amount of real time that it takes to complete the task but it doesn’t change the computational complexity of the algorithm. – ColGraff Jun 6 '17 at 15:39
• @ColGraff: It changes the time complexity from $O(c \cdot r)$ to $O(log c + log r)$. – Jörg W Mittag Jun 6 '17 at 21:12
• @JörgWMittag Computational complexity, or “time complexity” is not the real-world time used in an algorithm. It’s the total amount of work needed to compute the result. Even if you split that work among threads you still have the same amount of work, or total time. It doesn’t matter how much you run that task in parallel. See: Introduction to Algorithms, p. 779, "Performance measures" "The work of a multithreaded computation is the total time to execute the entire computation on one processor." – ColGraff Jun 6 '17 at 21:49

To compute the exact mean (no confidence interval or estimate) of each exam, you must at least observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this for, this problem should take at least $\Omega(c \cdot r)$ time.

• The only way to do this faster (but at a loss of accuracy, as implied by the answer) is to do random sampling to produce an estimate. Now you get to bring statistics into it instead of basic arithmetic - yay! – Baldrickk Jun 6 '17 at 16:15
• If you already have the current average pre-calculated and the count of exams, you can calculate what the new average would be with one additional student's exam in constant time. – Shufflepants Jun 6 '17 at 18:04

I'm only looking at the mean of a set of numbers, the Student x Class is an unnecessary detail of the problem.

Assuming the data $d[1..n]$ sorted (this costs already a hefty $\Theta(n \log n)$) and and error margin $\epsilon$ of the acceptable result, we compute recursively the sum of $d$, $\sum_{x \in [a,b]}d[x]$ as:

$d[a]$ if $a=b$

$(b-a)(d[b]+d[a])/2$ if $\frac{d[b]-d[a]}{b-a} \lt \epsilon$

$\sum_{x \in [a, \frac{a+b}{2}]} d[x] +\sum_{x \in [\frac{a+b}{2},b]} d[x]$ otherwise

For a "large enough" $\epsilon$ or for large sets of repeating data, the method goes by $O(n / \log(n))$.

This guarantees (the proof by induction is left as an exercise to the reader) the average (total sum divided by numbers) to be within plus minus $\epsilon$. Statistical methods involving sampling only guarantee you to be within a specified range according to both the confidence level and conformity of the distribution with the one you assert it may fit (such as uniform or normal distribution).

• A few details seems to be missing here. In particular, is the error margin relative and absolute? What is the connection between $\epsilon$ and the worst-case running time? Why are you mentioning statistical methods, while giving a deterministic algorithm? – Yuval Filmus Jun 6 '17 at 20:36
• @Yuval: the epsilon in my approach is absolute. Meaning you decide epsilon to be zero, you get the exact answer. You decide epsilon to be 0.5, expect the answer is in the interval [r-0.5, r+0.5], with r the true value. I've mentioned the statistic algorithms as a reaction to the existing comments. – Razvan Popovici Jun 7 '17 at 20:18