Time and Space Complexity of my Algorithm

Question

I want to know what the time and space complexity of my algorithm will be. The input is a list of songs, and the output is the longest list of songs in which the last word of a song is the same as the first word of the next song. So for example, if input is

test_list = ["Every Breath You Take", "Down By the River", "River of Dreams", "Take me to the River", "Dreams",
             "Blues Hand Me Down", "Forever Young", "American Dreams", "All My Love", "Cantaloop", "Take it All",
             "Love is Forever", "Young American"]

the output will be

['Every Breath You Take', 'Take it All', 'All My Love', 'Love is Forever', 'Forever Young', 'Young American', 'American Dreams', 'Dreams']

One caveat is that if there are two possible chains with equal length, then I will return the chains that comes alphabetically first

Here is my code

def song_chain(song_list):
    def chain(start, song_list):
        remaining = list(song_list)
        del remaining[remaining.index(start)]
        possibles = [x for x in remaining if x.split()[0] == start.split()[-1]]
        max_chain = []
        
        for c in possibles:
            l = chain(c, remaining)
            if len(l) > len(max_chain):
               max_chain = l
            if len(l) == len(max_chain):
                for i in range(len(l)):
                    selected = None
                    if l[i] != max_chain[i]:
                        selected = min(l[i], max_chain[i])
                    if selected == l[i]:
                        max_chain = l
        return [start] + max_chain
    
    return chain(song_list[0], song_list)

Answer 1

At each step, you call your at most n recursion calls (when all songs are possible) and for each of those calls, your algorithm takes O(n^2) to process (the double loops) so we get the following relation where:

T(n) <= n * T(n - 1) + O(n^2)
      = n * (n - 1) * T(n - 2) + O(n^2) 
      ....
      = n! T(0) + a O(n^2)

So the time complexity is O(n!).

For space, it always helps to think of the recursion tree which, in the worst case, will have depth n, when there's always a match and at each depth we store a list of size n-d (d is depth) so space is O(n^2).