CODEWITHSUNDEEP
arraysruntimesum
Javier Duluc
Javier Duluc

Reputation: 41

Running time for an algorithm that sums up integers

I am having trouble on an assignment regarding running time.

The problem statement is: "Isabel has an interesting way of summing up the values in an array A of n integers, where n is a power of two. She creates an array B of half the size of A, and sets B[i] = A[2i] + A[2i+1], for i=0,1,…,(n/2)-1. If B has size 1, then she outputs B[0]. Otherwise, she replaces A with B, and repeats the process. What is the running time of her algorithm?"

Would this be considered a O(log n) or a O(n)? I am thinking O(log n) because you would keep on dividing the array in half until you get the final result and I believe the basis of O(log n) is that you do not traverse the entire data structure. However in order to compute the sum, you have to access each element within the array thus making me think that it could possibly be O(n). Any help in understanding this would be greatly appreciated.

Upvotes: 3

Views: 1062

Answers (2)

mgibsonbr
mgibsonbr

Reputation: 22007

As you figured out yourself, you do need to access all elements to compute the sum. So your proposition:

I believe the basis of O(log n) is that you do not traverse the entire data structure

does not hold. You can safely disregard the possibility of the algorithm being O(log n) then.

As for being O(n) or something different, you need to think about how many operations will be done as a whole. George Skoptsov's answer gives a good hint at that. I'd just like to call attention to a fact (from my own experience) that to determine "the running time" you need to take everything into account: memory access, operations, input and output, etc. In your simple case, only looking at the accesses (or the number of sums) might be enough, but in practice you can have very skewed results if you don't look at the problem from every angle.

Upvotes: 2

George Skoptsov
George Skoptsov

Reputation: 3971

I believe the basis of O(log n) is that you do not traverse the entire data structure.

There's no basis for beliefs or guesses. Run through the algorithm mentally. How many recursions are there going to be for array A of size n? How many summations are there going to be for each recursion (when array A is of size n)?

  • First run: n/2 summations, n accesses to elements of A
  • .
  • .
  • .
  • Last run: 1 summation, 2 accesses to elements of A

How many runs are there total? When you sum this up, what is the highest power of n?

Upvotes: 2

Related Questions