time complexity

[218pE3v7]

hey
so im trying to find the time complexity(exact) for recursive binary search and having some trouble the left is a code snipet and right is what I think of time

if low > high
return nil
mid=(low+high)/2
if(v==a[mid])
return mid
else if(v>a[mid])
recursivesearch(a,v,mid+1,high)
else
recursivesearch(a,v,low,mid+1)


so im not sure the time for the if and else if and else would they be just 1 since we just checking a condition or would it be n+n/2+n/4+... ? since we are gonna have to do it multiple times?

then my return statements i think its just 1
my single operation statements i think its 1 too

now the recursive calls would it be n/2 or would it be like n/2+n/4+... and also include the if and else if conditions?

[keskiverto]

The standard library focuses on some details of complexity: http://www.cplusplus.com/reference/algorithm/binary_search/

[Ganado]

Things like simple comparisons, arithmetic, returning from a function, are all constant complexity, correct.

recursivesearch(a,v,mid+1,high) // I'm thinking it is n/2 but ...

This is where we need to look further. I assume the code excerpt you're looking is the recursivesearch function itself.

I can see why your guess is n/2, but you have to think about all the iterations/recursions happening as a whole, and not just an individual recursion.
When recursivesearch is called, the search space of your function is reduced by about half.
However, this recursivesearch is applied repeatedly until the result is narrowed down to match.

If you start at some number n, say 100, then each time you apply the recursive search to a half of the search space, your search space will decreases (roughly) like: 50, 25, 13, 7, 4, 2, 1.
So it takes around 7 or less iterations to narrow in on to a single number.

If you start with n = 1000, you'd get something like: 500, 250, 125, 63, 32, 16, 8, 4, 2, 1.
It will take 10 or less iterations to narrow in on a particular number.

As you can see, even though n was increased by a whole magnitude (100 --> 1000), the number of iterations to find a number only increased from 7 to 10. We can repeat this for even greater numbers and see a similar pattern, e.g. 10000 --> 5000, 2500, 1250 (and now we're back at around 1000). So it's not linear O(n), or some multiple of a linear number.

What's actually happening is that when you repeatedly reduce the search space by 1/2 each time, it ends up taking roughly log₂(n) iterations to complete. In complexity notation, this is O(log n) because factors that are asymptotic to 1 don't matter. This is very advantageous over O(n) for large sets of data.