amchacon - 1 year ago 107
C++ Question

# Cost of an algorithm

The problem is the next:

We want to know the size of an vector, we can't use size() but we have a function inBounds(vector& arr,int index) that returns true if the index is a valid position of the vector.

So, my approach is iterate positions. Starting at 1 and duplicating (2,4,8,16,32...) until that inBounds returns false, step back so and repeat the search in the subrange.

Let's do an example, put N = 21:

• 1 = True

• 2 = True

• 4 = True

• 8 = True

• 16 = True

• 32 = False

Step back to 16, and search in 16-32 range:

• (16+1) = True

• (16+2) = True

• (16+4) = True

• (16+8) = False

Step back to 20 (16+4) and start over:

• (20+1) = True

• (20+2) = False

Start over in 21:

• (21+1) = False

Ok, so the size is 21.

This is my implementation in code:

#include <iostream>
#include <vector>
using namespace std;

int inBounds(const vector<int>& arr,int i)
{
return i < arr.size();
}

int size(const vector<int>& arr)
{
int init = 0;

while (inBounds(arr,init))
{
int start = 2;
while (inBounds(arr,init+start))
{
start *= 2;
}
start /= 2;
init += start;
}
return init;
}

int main()
{
vector<int> arr;

for (int i = 0;i < 1000;i++)
{
arr.resize(i);
int n = size(arr);
if (n != arr.size())
cout << "FAIL " << arr.size() << ' ' << n << endl;
}
return 0;
}

This works good. But i don't know the exactly cost of this algorithm. The first search is indeed log(N), but now i need to add the subrange searchs. So i have my doubts about the real cost