algorithm for calculating the sum of value in the Array and Big O Notation

Question

How to find an algorithm for calculating the sum value in the array?? Is is Something like this?

Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
      sum := sum + a[J]
      j:=j+1
  end while
end Algorithm Array Sum

And how I can relate it with the running time of the algorithm by using O-Notation

This is the past year exam and I need to make revision for my exam.

Question
An Array A[] holding n integer value is given
1.Give an algorithm for calculating the sum of all the value in the array
2.Find the simplest and best O-notation for the running time of the algorithm.

Thank!

Answer 1

Since n is the size of array and all you have to do is iterate from begeinning to end the the Big O notation is O[n]

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 2

I think that you meant "while j <= N", you need to specify this.

The running time shall be O(n), I think, as you have only one loop.

Answer 3

The question is to find the sum of all the values so iterate through each element in the array and add each element to a temporary sum value.

temp_sum = 0
for i in 1 ...array.length
    temp_sum = temp_sum + array[i]

Since you need to go through all the elements in the array, this program depends linearly to the number of elements. If you have 10 elements, iterate through 10 elements, if you have a million you have no choice other than to go through all the million elements and add each of them. Thus the time complexity is Θ(n).

If you are finding the sum of all the elements and you dont know any thing about the data then you need to look at all the elements at least once. Thus n is the lowerbound. You also need not look at the element more than once. n is also the upper bound. Hence the complexity is Θ(n).

However if you know something about the elements..say you get a sequency of n natural numbers, you can do it in constant time with n(n+1)/2. If the data you get are random then you have no choice but do the above linear time algorithm.

Answer 4

To calculate O for this algorithm you need to count the number of times each line of code executes. Later on you will only count the fundamental operations but start by counting all.

So how many times will the j := 1 line run? How many times will the sum := 0 run? How many times will the while loop's condition execute? The statements inside the while loop?

Sum these all up. You will notice that the value you get will be something like 1 + 1 + n + n + n = 2 + 3n. thus you can conclude that it is a linear function on n.