c++ - Cost of an algorithm -

the problem next:

we want know size of vector, can't use size() have function inbounds(vector& arr,int index) returns true if index valid position of vector.

so, approach iterate positions. starting @ 1 , duplicating (2,4,8,16,32...) until inbounds returns false, step , repeat search in subrange.

let's example, put n = 21:

• 1 = true
• 2 = true
• 4 = true
• 8 = true
• 16 = true
• 32 = false

step 16, , search in 16-32 range:

• (16+1) = true
• (16+2) = true
• (16+4) = true
• (16+8) = false

step 20 (16+4) , start over:

• (20+1) = true
• (20+2) = false

start on in 21:

• (21+1) = false

ok, size 21.

this implementation in code:

#include <iostream> #include <vector> using namespace std;  int inbounds(const vector<int>& arr,int i) {     return < 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;      (int = 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. don't know cost of algorithm. first search indeed log(n), need add subrange searchs. have doubts real cost

actually, worst case scenario o(log(n)²) (which sorta expected, since have o(log) cycle nested inside log cycle)

to understand why, try narrow down 31 (2ⁿ-1 in general case)

let's example, put n = 31:

1 = true 2 = true 4 = true 8 = true 16 = true 32 = false 

o(log(n)) here, alright, nobody contests it

--

now count steps

step 16, , search in 16-32 range:

(16+1) = true (16+2) = true (16+4) = true (16+8) = true (16+16) = false  

(4+1) steps - log(32/2)+1 = log(32)

step @ 24

(24+1) = true (24+2) = true (24+4) = true (24+8) = false 

(3+1) steps - log(16/2)+1=log(16)

step @ 28:

(28+1) = true (28+2) = true (28+4) = false 

(2+1) steps - log(8/2)+1=log(8)

step @ 30

(30+1) = true (30+2) = false 

(1+1) steps log(4/2)+1=log(4)

result: (4+3+2+1=10 steps in positive + 4 in negative). or, in form log(32)+log(16)+log(8)+log(4)+log(2) - 1 =log(32)(1+1/2+1/3+1/4+1/5)-1. ignore -1 @ end , formula becomes

log(n)*(1+1/2+1/3+1/4+...+1/n)

well, large n-es, harmonic series divergent , asymptotic behaviour logarithmic.

so got nice o(log(n)*log(n)) complexity.

qed(??)