0

I have an array of n characters. To calculate the sum of the array I have used the following code snippet:

  var arr = [1,2,3,4,5,6]
  var i = 0;
  var j = arr.length - 1;
  var sum = 0;
  while(i<j || i==j){
     sum = sum + ((i==j) ? arr[i] : arr[i] + arr[j])
     i++;
     j--;
  }

I have used two pointers i and j to traverse the array from both directions and it finds the sum. I wanted to know whether this is a correct approach and does it run in O(log n) time complexity?

Thanks

Red Devil
  • 45
  • 3
  • 7
  • 3
    your code runs in n/2 => O(n) time complexity. – Anshul Jul 03 '20 at 18:47
  • 1
    You can simply put a counter in your while loop. With an array of 100, that counter would be 50, while if it were O(log n) it would be closer to `Math.log2(100)` ~= 6. If you could find a way to do this in `O(log n)` for arbitrary arrays you would become famous. – Mark Jul 03 '20 at 18:50
  • 1
    Related: https://stackoverflow.com/questions/1230233/how-to-find-the-sum-of-an-array-of-numbers – str Jul 03 '20 at 18:52
  • As you need to read all *n* values to calculate the sum, you cannot possibly get below O(n), whichever the order with which you read those values. – trincot Jul 03 '20 at 19:20

1 Answers1

2

Although it may seem like the complexity of your algorithm is less than O(N), it is actually still is O(N). Since you are only incrementing/decrementing by a factor of 1, the number of iterations in your loop would be about N / 2 which is O(N).

You would achieve O(log N) time complexity if you disregarded half of N after each iteration as shown in an algorithm like binary search.

For this summation problem, you can actually solve in O(1) time by using math. See: this wikipedia page.

EDIT: you can only use math for 1 to N

Marlo D
  • 56
  • 2