Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find the average of a list of numbers in O(1) notation - constant time

Here's the thing, I have a task to make an array with some numbers, after that the array can accept any other numbers of the the same type inside on any position. When I get the final array (with the added numbers) I need to find the average of the numbers inside with a constant O(1) time. How do I do that?! Here's what I have as an example

Elements: 5 12 7 9 31 Average: 12.8

like image 616
Filip Kangalov Avatar asked Dec 18 '25 07:12

Filip Kangalov


1 Answers

If this is an array class you can keep track of the sum of all of the numbers as they are added and updated. Then when all updates are complete just divide the sum by the number of elements to get the average, and just the calculation of the average will be O(1) since the sum was precomputed.

If this is a raw memory array that you are simply passed, then calculating the average will require summing all of the number, which is an O(N) unless someone is playing a semantics game regarding what an operation is.

like image 97
Josh Heitzman Avatar answered Dec 19 '25 22:12

Josh Heitzman



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!