amchacon amchacon - 26 days ago 9
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

Answer

seems like your first subrange search is also logN (since it uses basically same algorithm as the initial part) while your final subrange search is linear (iterating over every value), but it's very much bounded and a small fraction of N. i would say your algorithm is roughly c * logN, where c is a small value representing the number of subsearches you're doing, so O(logN) in general.