Question

Isabel has an interesting way of summing up the values in a sequence A ofn integers, where n is a power of two. She creates a new sequence B of halfthe size of A and sets B[i] = A[2i]+A[2i+1], for i = 0,1, . . . , (n/2)−1. IfB has size 1, then she outputs B[0]. Otherwise, she replaces A with B, andrepeats the process. What is the running time of her algorithm?

Answer 1

Answer:

Running time of algorithm is O(n).

Explanation:

n is power of 2

n =2,4,8,16,32,...................................

A is an array having n elements

B is an array of size 0 to (n/2)-1

if n=4 B then (4/2)-1 =1 So B has size 2

for(i=0;i<=(n/2)-1;++)

{

B[i]=A[2i]+A[2i+1];

}

This for loop will run n/2 times so complexity in terms of Big Oh is O(n/2) =O(n)

Running time of algorithm is O(n).