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
```

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?