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

Question

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!

Answer 1

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