Proof time complexity -

i'm trying determine complexity of 2 functions, d in integer , list list of integers:

def solve(d, list):     element in list:       dofunc(element, d, list)  def dofunc(element, d, list):   quantityx = 0    if(d > 0):     otherelement in list:       if otherelement == element:         quantityx += 1     return quantityx + (dofunc ((element+1), (d-1), list))   return 0 

intuitively, think has o(n²) n quantity of elements of list, i'd proof in formal way.

first observation: solve calls dofunc, not other way around. therefore, complexity of solve depend on complexity of dofunc, not other way around. need figure out complexity of dofunc first.

let t(e, d, n) time complexity of dofunc function of e, d , number of elements n in list. every time dofunc called, n iterations of loop , invoke dofunc e+1, d-1, , list unchanged. based on this, know time complexity of dofunc given following recursive formula:

t(e, d, n) = + b + t(e+1, d-1, n)

here, a , b constants determined.

now need base case recursive formula. our base case, time don't recurse, when d <= 0. assuming d non-negative, means d = 0 base case. following additional requirement:

t(e, 0, n) = c

here, c constant determined.

putting together, can list out few values different values of d , see if can identify pattern:

d    t(e, d, n) 0    c 1    c + b + 2    c + 2b + 2an 3    c + 3b + 3an ... k    c + kb + kan 

based on this, can guess t(e, d, n) = c + db + adn constants a, b, c. can see formula satisfies base case , can check satisfies recursive part (try this). therefore, our function.

assuming e, d , n independent , vary freely, time complexity of dofunc best rendered o(c + db + adn) = o(dn).

since solve calls dofunc once each element in list, complexity n times of dofunc, i.e., o(dn^2).