How is this basic algorithm O(n)?

Question

int G(int a[], int n) {
int x=0, i, j;

 for(i=1; i<n; i=i*2){
 for(j=0; j<i; j++)
     x += a[j];
 }
 return x;
}

How is the worst case tight bound on this algorithm O(n). Is the first loop not executed O(log(n) times and the second for loop executed O(n) times giving O(n logn)?

Answer 1

O(n) means an algorithm ultimately requires at most some number of steps proportional to n when its input size is n. The inner loop is O(n) in this characterization, but its input size is i, so it requires some number of steps proportional to i.

Add up how many iterations of the inner loop are performed. If n is exactly a power of two, that is 1 + 2 + 4 + 8 + … + n/2. The sum of that series is n-1. Thus, the entire program performs n-1 iterations when its input size is n. So it is O(n).

(If n is not exactly a power of two, the number of iterations is p-1, where p is the least power of 2 not less than n. p-1 is less than 2*n, which is proportional to n, so the program is still O(n).)