Proof time complexity for recursive function

Question

I'm trying to determine the complexity of this function, where D and element are integers and list is an ordered list of integers. Note from this that (otherElement-element) will be strictly positive.

def doFunc(element, D, list):
  x = 0 
  if(D > 0):
    for otherElement in list:
      if otherElement == element:
        x += 1
      if otherElement > element:
        return x + (doFunc (otherElement,D-(otherElement-element) , list))
  return x

Given that the list will not be always fully iterated, I don't know how can I determine a time complexity for this function.

Answer 1

doFunc checks the list from left to right to find an otherElement greater than or equal to the provided element. At most one recursive call is made. We can try to figure out the worst-case time complexity of this function by deducing what must be the worst-case input and analyzing the behavior.

Suppose we start with a list of size 1; call it {1}. If we call the function on this list, what's the most iterations we could possibly get out of the for loop? Well, if we set element = 1, we get a single iteration. However, if set element = 0, we can get doFunc to recursively call itself with element = 1; this means we get two iterations. Convince yourself that there's no way we can ever get more than two iterations out doFunc for this list. Also convince yourself that the choice of {1} is essentially unimportant; any single-element list would work the same way.

Suppose now that we want to find a worst-case list of length 2; should the next number be the same, greater, or smaller? Consider {1, 1}, {1, 2} and {1, 0}. Calling doFunc with element = -1 will cause at most 3, 5, and 3 iterations, respectively, of the for loop. Adding a greater element results in the worst possible behavior for a list of length 2.

Convince yourself that the worst case is an ascending list of numbers; in fact, due to the limiting factor of D, the worst-case is a list of the form {a, a+1, a+2, ..., a+n-1} of n elements. For such a list, we have the following behavior when setting element < a:

1. One iteration on the initial call to doFunc; we then have otherElement > element, so we recursively call doFunc.
2. Two iterations on the first recursive call to doFunc; we then have otherElement > element, so we recursively call again.
3. Similarly, on the kth recursive call to doFunc, we should expect k+1 iterations of the for loop. Since the for loop can't iterate more than n times in the context of a single invocation, this means that we have at most n - 1 recursive calls to doFunc.

We have 1 + 2 + ... + n = O(n^2). This is assuming that d > n. Assuming d < n, we can't get all of the recursive calls; we can have, at most, 1 + 2 + ... + d iterations in this case, or O(d^2). Therefore, the worst-case behavior of this function is O(min(n^2, d^2)). The complexity of the thing in your other question was O(dn), which is worse than the complexity here, unless d = n, in which case the performance is the same.

EDIT: note also that the constants for the time complexity here are virtually guaranteed to be significantly better than for your other attempt, so you'd see noticeably better performance despite having the same asymptotic complexity.