-2

What is the complexity of calculating the arithmetic mean in big O notation? Please also add a short explanation how you get to the result.

F.M.F.
  • 1,929
  • 3
  • 23
  • 42
  • What have you tried so far? Is this homework? – templatetypedef Jul 17 '19 at 17:52
  • I thought this is an Q&A site... I did google it but couldn't find an answer. If someone else now googles it he finds this. Mission accomplished I would say... (This is no homework btw) – F.M.F. Jul 17 '19 at 17:59
  • Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Prune Jul 17 '19 at 18:22
  • Welcome to StackOverflow. Please follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](https://stackoverflow.com/help/on-topic), [how to ask](https://stackoverflow.com/help/how-to-ask), and ... [the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. StackOverflow is not a design, coding, research, or tutorial resource. It is *not* a general Q&A site, as the guidelines describe. – Prune Jul 17 '19 at 18:23
  • 2
    @F.M.F. I didn't downvote, but I was tempted to. If you read the tool tip when you hover over the downvote arrow, it says "This question does not show any research effort..." I believe this applies to your question. – beaker Jul 17 '19 at 18:54

1 Answers1

4

Assuming, you are referring to the mean here: https://en.wikipedia.org/wiki/Arithmetic_mean

It is always going to be O(N). Reason? Simply put, calculating a mean includes doing a summation of all the elements in your set and the further dividing it by N. Now if you take simplest approach and do as stated then you have to iterate through each element in the set.

Now, let's assume that you are being a little smarter about it and doing a divide and conquer on that meaning you divided the set into smaller sets, and then claculated mean and then did a mean of the calculated means. In this case it could be O(N/2) + O(N/2) + O(LogN)[which is the cost to calculate mean of the means] = O(N + LogN). In this case, doing the simple mean would be cheaper O(N).

Hopefully that makes sense.

Lost
  • 12,007
  • 32
  • 121
  • 193
  • Thank you for the answer. Do you have an idea on what was wrong with my question/ why it was downvoted? – F.M.F. Jul 17 '19 at 17:44
  • 2
    While I did not downvote it, it would be very very difficult to mind-read the down-voter. However, as a side comment, I would say try to include more details in your question. Details like what have you already tried, what is your thought process, what do you already know and what is the missing gap. SO users like to see some homework done before they spend some time. Just an observation. I personally try to answer if I understand the question. – Lost Jul 17 '19 at 17:50
  • I'm trying to understand how you could calculate the mean of N items in O(N/2). If you split into two arrays and calculate the mean of each, then did a mean of the two calculated means, you'd still have to look at all N elements. And you'd have to do one extra mean calculation. If you did it recursively as I think you're suggesting, the algorithm would be O(N + log N), whereas the simple method is, simply O(N). And that's a tight bound: you will *never* be able to compute the mean of an array of values in fewer than N operations. – Jim Mischel Jul 18 '19 at 02:56
  • @JimMischel : you are right. Sorry for the mistake. I updated my answer. – Lost Jul 18 '19 at 05:06
  • By the way, a "mean of calculated means" is not the same as the mean of the entire set. Consider, for example, the array `[1,7,3,4,11]`. The mean of 1 and 7 is 4. The mean of `[3,4,11]` is 6. Add them together and divide by 2, and you get 5. But `1+7+3+4+11 = 26`, giving a mean of 5.2. – Jim Mischel Sep 27 '19 at 23:23