# Complexity analysis of binary search over binary indexed tree I’m performing a binary search over the binary indexed tree and the code as shown below:

``````void update(vector<long long>& bit, const long long val, long long idx) {
for(long long i = idx; i < bit.size(); i += i & (-i)) {
bit(i) += val;
}
}

long long query(vector<long long>& bit, long long idx) {
long long sum = 0;
while(idx > 0) {
sum += bit(idx);
idx -= idx & (-idx);
}
return sum;
}

void build_bit(vector<long long>& arr, vector<long long>& bit) {
long long size = arr.size();
for(int i = 1; i <= size; ++i) {
update(bit, arr(i - 1), i);
}
}

long long bfind(vector<long long>& bit, const long long val) {
long long left = 1;
long long right = bit.size() - 1;
long long ans = -1;
long long m = -1;
while(left <= right) {
m = left + ((right - left) >> 1);
long long sum = 0;
bool found = 1;
for(long long i = 0; i < (bit.size() - m); ++i) {
if(i > 0) {
sum = query(bit, i + m) - query(bit, i);
} else {
sum = query(bit, i + m);
}
if(sum > val) {
found = 0;
break;
}
}
if(found) {
ans = m;
left = m + 1;
} else {
right = m - 1;
}
}
return ans;
}
``````

My main doubt is about the complexity of the algorithm implemented inside bfind.

Here are my calculations of the complexity.
The first while loop takes O(logN) time.
The image attached below shows the size with which the second cycle operates during each iteration: Taking into account that query operation of BIt takes O(logN) time the overall complexity for the second loop will be O(nLogN).

So the total complexity of the bfind algorithm will be O(N logN logN).
Is this correct? Am I missing something? Posted on Categories Articles