current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

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 <= 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: is this code's worst-case complexity log(n)? If not, what should I do differently?

share|improve this question

5 Answers 5

up vote 4 down vote accepted

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).

  1. This means each number in the list is at least 1 larger than the previous number.

  2. Assume that list[k] == x < k. Because the numbers are strictly increasing it must be that list[k-1] <= x-1 < k-1, list[k-2] <= x-2 < k-2, ... list[k-l] <= x-l < 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.

  3. Assume that list[k] == x > k. Because the numbers are strictly increasing it must be that list[k+1] >= x+1 > k+1, list[k+2] >= x+2 > k+2, ... list[k+l] >= x+l > 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

  1. Start 0 <= s < ms with list[s] < s
  2. Middle ms <= m < me with list[m] == m
  3. End me <= e < n with list[e] > 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] < k and the smallest index for which list[k] > 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))

share|improve this answer
    
Where did you get that the numbers are 0 or positive? Dropping that restriction does not break your reasoning: it would just be necessary to find both the smallest and the largest index for which list[k] == k. –  Janne Karila Nov 21 '13 at 8:13
    
@JanneKarila: Hm, true good point, I'll adjust my answer –  ChrisWue Nov 21 '13 at 8:14
    
+1, but this does not seem to show that the posted code has a worst case complexity of O(log n). –  Gareth Rees Nov 21 '13 at 18:36
    
@GarethRees: Good point, totally forgot about it –  ChrisWue Nov 21 '13 at 18:55
    
Disagreed with your Update; the third return skips checking the middle items when examining a fully-matched subrange, so avoids counting each element. Similarly the other returns skip checking ranges that are fully unmatched. In cases that are neither, it splits it in half and tries each half; why aren't most ranges one or the other? (I.e. what sequence characteristics would provoke O(n) runtime?) –  Michael Urman Nov 23 '13 at 2:28
up vote -1 down vote

I don't know enough Python to comment on your code, but returning a count of where array[index] == index, should be O(n). And as I said, I dunno Python, but it looks like you are making this a lot more complicated than it is. It could be as simple as

function foo(array) {
    int count = 0;
    for(int i = 0; i < array.length; i++) {
        if(array[i] == i) count++;
    }
    return count;
}

Or maybe I just don't understand what you're trying to accomplish...

share|improve this answer
1  
The function's complexity must be log(n) in the worse case. –  user32385 Nov 20 '13 at 15:27
    
If you mean O(n), then yes. If you mean O(log n) then no. If you mean something else I'm not sure, sorry. –  Max Nov 20 '13 at 15:30
    
What you're missing is that the list is sorted and its elements are unique integers. That allows a O(log n) solution. –  RemcoGerlich Nov 23 '13 at 21:45
    
@RemcoGerlich ok, thanks :) –  Max Nov 24 '13 at 15:24
up vote 0 down vote

Because you have a sorted list without numbers duplicates there are several things you can do to optimize the approach.

If your list was not sorted then you would need to check every element O(n) (nothing sorts random list faster than that so you can't 'cheat' sort it first); or if duplicates were allowed then you there could be several independent sections of the list that are continuous and you would need to account for that in your implementation (which would dramatically affect performance).

But as this is a sorted list without duplicates, we can know that there can only be a single section of the list that is continuous, the task then becomes an exercise in finding the start and end of this.

To this end what you need to do is start in the middle of the array and then walk up/down the array moving by half the length of the array section at any time.

By doing this approach you achieve O(log n) performance provided duplicates are not allowed, this is effectively what you have in your question.

While you can sit down and prove this mathematically, but for more complex situations you can quickly verify your suspicions with a brute-force approach by thinking under what situations would your code perform worst, then do some benchmarks with greatly varying size of arrays, then compare the run-time versus the size of the array.

share|improve this answer
    
Doesn't meet the constraints; the code presented has to be O(log n) or faster. –  Snowbody Nov 20 '13 at 21:46
    
why the -1? this code is considered O(log n) because that is the average time, and the worst case is O(n) –  Seph Nov 21 '13 at 3:17
    
because the problem as stated asks for O(log n) worst-case time –  Snowbody Nov 26 '13 at 21:55
up vote -1 down vote

Ignoring the print, I believe the offered code does operate in O(log n) time. Here's what I see the code doing. It assumes the list it receives is sorted, and consists of no repeated integers (I believe this is what you meant by "sorted list with different numbers")

  1. Constant time checks on the beginning, end, and middle of its range
  2. An extraneous print (ignoring this, as I think it makes it O(n log n); certainly the first hit will read and copy the entire list taking O(n))
  3. Up to two recursive calls that evaluate half or fewer of the elements in the existing range; this results in O(log n) calls

Other comments:

  • I would be strongly tempted to cut down on the quantity of code by omitting the checks related to middle. I would let the first three checks suffice as base cases, and always recurse on both full halves of the list.
  • Consider using a single function by defining default argument values, e.g. def foo(lst, start=0, end=-1): ... and handling -1 specially (if end == -1: end = len(lst)-1).
  • Consider matching python's half open ranges for your start and end parameters (passing len(lst) instead of len(lst)-1 and adjusting the offsets accordingly). This might make things better or might make them worse. I'm not sure.
  • Use a more descriptive name than foo for your function.

Note that the first two comments are probably trading away performance for simplicity of code. While I almost always prefer this trade-off, there are cases where performance is more important.

share|improve this answer
up vote 0 down vote

  1. You have a bug in the code. You should check both start and end values, not the absolute difference.

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

  2. The worst-case complexity can't be O(n) because for each iteration, you can't guarantee that the algorithm will call only half. For each iteration, it can call 1+foo_helper(fist half)+foo_helper(second half), which is two halves, many times.

share|improve this answer
    
Yeah, but how many is "many"? By its very nature the partitioning will bottom out quite quickly either in the "the two ends match" case or the "way off" caase. –  Snowbody Nov 20 '13 at 21:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.