N+N/2+N/4... iteration runtime

Question

I'm looking at a code example that iterates through an array of size N.

• First iteration, I'm going through all the elements -> N
• Next iteration, I'm only going through half of the array -> N/2
• ...

This goes on until the size of the array I have to go through reaches 1.

Would the runtime for this be O(N)? or O(NlogN)?

I thought it would be O(NlogN), but the book says it is only O(N).

Answer 1

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3};

  for (unsigned n(v.size()); n; n /= 2)
  {
    for (unsigned i(0); i < n; ++i)
      std::cout << v[i];

    std::cout << std::endl;
  }
}

This program prints part of π on each line (first line n digits, ..., last line 1 digit):

3141592653589793

31415926

3141

31

3

The total number of digits it prints is 31 = v.size() * 2 - 1.

In general, given a vector of size N (N = 2^k), the inner instruction (std::cout << v[i]) is executed 2N - 1 times (O(N)):

N + N/2 + N/4 + ... + 2 + 1 = 2N - 1

If N isn't a power of two, you have to introduce some small adjustments to the formula, but the complexity stays the same.