CODEWITHSUNDEEP
time-complexityproof
FranckN
FranckN

Reputation: 133

Proof time complexity

I'm trying to determine the complexity of this two functions, where D in an integer and list is a list of integers:

def solve(D, list):
    for element in List:
      doFunc(element, D, list)

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

Intuitively, I think it has a O(n²) where n is the quantity of elements of list, but I'd like to proof it in a formal way.

Upvotes: 1

Views: 124

Answers (1)

Patrick87
Patrick87

Reputation: 28292

First observation: solve calls doFunc, but not the other way around. Therefore, the complexity of solve will depend on the complexity of doFunc, but not the other way around. We need to figure out the complexity of doFunc first.

Let T(E, D, N) be the time complexity of doFunc as a function of E, D and the number of elements N in the list. Every time doFunc is called, we do N iterations of the loop and then invoke doFunc with E+1, D-1, and the list unchanged. Based on this, we know that the time complexity of doFunc is given by the following recursive formula:

T(E, D, N) = aN + b + T(E+1, D-1, N)

Here, a and b are some constants to be determined.

Now we need a base case for this recursive formula. Our base case, the only time we don't recurse, is when D <= 0. Assuming that D is non-negative, this means D = 0 is the base case. We get the following additional requirement:

T(E, 0, N) = c

Here, c is some constant to be determined.

Putting this all together, we can list out a few values for different values of D and see if we can identify a pattern:

D    T(E, D, N)
0    c
1    c + b + aN
2    c + 2b + 2aN
3    c + 3b + 3aN
...
k    c + kb + kaN

Based on this, we can guess that T(E, D, N) = c + Db + aDN for some constants a, b, c. We can see that this formula satisfies the base case and we can check that it also satisfies the recursive part (try this). Therefore, this is our function.

Assuming E, D and N are all independent and vary freely, the time complexity of doFunc is best rendered as O(c + Db + aDN) = O(DN).

Since solve calls doFunc once for each element in the list, its complexity is simply N times that of doFunc, i.e., O(DN^2).

Upvotes: 1

Related Questions