CODEWITHSUNDEEP
pythonalgorithmrecursioncomplexity-theorytime-complexity
davidjack
davidjack

Reputation: 3

Is my code's worse time complexity is log(n)?

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

def foo_helper(lst, start, end):

    if start > end:
        # end of recursion
        return 0

    if lst[end] < end or lst[start] > 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] < 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 if this code's worst-case complexity = log(n)?
If not, What should I do different?

Upvotes: 0

Views: 154

Answers (2)

twalberg
twalberg

Reputation: 62379

If you have a list of N numbers, all unique, and known to be sorted, then if list[0] == 0 and list[N-1] == N-1, then the uniqueness and ordering properties dictate that the entire list meets the property that list[i] == i. This can be determined in O(1) time - just check the first and last list entries.

The uniqueness and ordering properties force any list to have three separate regions - a possibly empty prefix region where list[i] < i, a possibly empty middle region where list[i] == i, and a possibly empty suffix region where list[i] > i]. In the general case, finding the middle region requires O(n) time - a scan from the front to find the first index where list[i] == i, and a scan from the back to find the last such index (or you could do both with one single forward scan). Once you find those, you are guaranteed by uniqueness and ordering that all the indexes in between will have the same property...

Edit: As pointed out by @tobias_k below, you could also do a binary search to find the two end points, which would be O(log n) instead of O(n). This would be the better option if your inputs are completely general.

Upvotes: 2

YXD
YXD

Reputation: 32511

To expand on my comment trying to think about this problem. Consider of the graph of the identity function, which represents the indices. We want to know where this sorted list (a strictly monotonic function) intersects the line representing the indices y = x, considering only integer locations. I think you should be able to find this in O(n) time (as commented it seems binary search for the intersection bounds should work), though I need to look at your code more closely to see what it's doing.

Because we have a sorted list with unique elements, we have i == list[i] either at no place

enter image description here

at one place

enter image description here

or if there are multiple places they must be consecutive (once you're above the line you can never come back down)

enter image description here

Code used:

import numpy as np
import matplotlib.pyplot as plt
a = np.unique(np.random.randint(-25, 50, 50))
indices = range(len(a))
plt.scatter(indices, indices, c='b')
plt.scatter(indices, a, c='r')
plt.show()

Upvotes: 2

Related Questions