count all array[index] == index occurrences The method foo gets a sorted list with different numbers as a parameter and returns the count of all the occurrences such that: i == list[i] (where i is the index 0 &lt;= i &lt;= len(list)).  

def foo_helper(lst, start, end):

    if start &gt; end:
        # end of recursion
        return 0

    if lst[end] &lt; end or lst[start] &gt; start:
        # no point checking this part of the list
        return 0

    # all indexes must be equal to their values
    if abs(end - start) == lst[end] - lst[start]:
        return end - start + 1

    middle = (end + start) // 2

    print(lst[start:end+1], start, middle, end)

    if lst[middle] == middle:
        #print("lst[" , middle , "]=", lst[middle])
        return 1 + foo_helper(lst, middle+1, end) + \
    foo_helper(lst, start, middle-1)


    elif lst[middle] &lt; middle:
        return foo_helper(lst, middle+1, end)
    else:
        return foo_helper(lst, start, middle-1)

def foo(lst):
    return foo_helper(lst, 0, len(lst)-1)


My question is: is this code's worst-case complexity log(n)?  If not, what should I do differently?
Now let's see if I understand your problem: Given a sorted list of unique numbers you want to find all instances where list[i] == i (the important part is the unique).


This means each number in the list is at least 1 larger than the previous number.
Assume that list[k] == x &lt; k. Because the numbers are strictly increasing it must be that list[k-1] &lt;= x-1 &lt; k-1, list[k-2] &lt;= x-2 &lt; k-2, ... list[k-l] &lt;= x-l &lt; k-l. So if you have an index where the value is smaller than the index then this must also be the case for all previous indices.
Assume that list[k] == x &gt; k. Because the numbers are strictly increasing it must be that list[k+1] &gt;= x+1 &gt; k+1, list[k+2] &gt;= x+2 &gt; k+2, ... list[k+l] &gt;= x+l &gt; k+l. So if you have an index where the value is larger than the index then this must also be the case for all following indices.


The conclusion from these points is that a list with the given properties can be divided into three parts


Start 0 &lt;= s &lt; ms with list[s] &lt; s
Middle ms &lt;= m &lt; me with list[m] == m
End me &lt;= e &lt; n with list[e] &gt; e


Your problem is to find the middle part. The number of items where list[i] == i is then me - ms.

This can be solved by finding the largest index for which list[k] &lt; k and the smallest index for which list[k] &gt; k (or the smallest and largest indices for which list[k] == k - depends on how you want to write the search criteria).

Using two binary searches should yield the desired results which will guarantee a worst case complexity of O(log(n))

Update: Your original implementation is effectively a binary search which will find both end and start point of the middle sequence so you implementation is O(log(n))