pythonalgorithmrecursiontime-complexitybacktracking

# What is time complexity of recursive function in a loop? Manually counting steps show 2^n but why?

So I got a problem to construct every possible collinear set of point from a given set of points. I managed to write a backtracking algorithm for the problem. However, I can't really show mathematically the time complexity. I got O(n!), but it seems incorrect, it run through too fast the example inputs. I counted it manually, came back as O(2^n) . Why is that number though? I don't have 2 recursive calls and my recursive call is inside a loop. How should I show mathematically this result?

I have here the whole algorithm, the questionable function is backtracking_recursive

``````# Check if three points are collinear
def check_if_collinear(point_A:tuple, point_B:tuple, point_C:tuple):
determinant = float(point_A[0] * (point_B[1] - point_C[1])+
point_B[0] * (point_C[1] - point_A[1])+
point_C[0] * (point_A[1] - point_B[1]))
triangle_area = 0.5 * determinant
return triangle_area == 0

# recursive backtracking to find sets of collinear points
# starts in the points list from index start, adds an element to current_set
# checks if lastly added element is collinear with first element and current point at index i
def backtracking_recursive(start:int, current_set:list, collinear_sets:list, points:list):
global counter
if len(current_set) > 2:
collinear_sets.append(current_set.copy())

for i in range(start, len(points)):
if not current_set or check_if_collinear(current_set[0], current_set[-1], points[i]):
current_set.append(points[i])
backtracking_recursive(i + 1, current_set, collinear_sets, points)
current_set.pop()

# helper function for solution
def find_collinear_sets(points:list):
collinear_sets = []
backtracking_recursive(0, [], collinear_sets, points)
return collinear_sets
``````

Thank you for your help!

Solution

• In the worst case (all points collinear) you build the whole power set, i.e., all 2^n subsets.

You'd get all n! permutations if you recursed with all but the i-th element, but you don't. You only recurse with the elements after the i-th.

Time complexity still isn't O(2^n) but O(n•2^n), though, as you copy the non-trivial subsets and their average length is ~n/2.

Another way to count the number of subsets you build: Let C(n) the number of subsets you build with n (remaining) elements. We have C(n) = 2^n, and can show it like this, where the `1` comes from the subset corresponding to the current call and the `C(n-1)` to `C(0)` reflect the recursive calls:

``````C(n) = 1 + (C(n-1) + ... + C(0))
= 1 + (2^(n-1) + ... + 2^0)
= 1 + (2^n - 1)
= 2^n
``````