Qual é o grande momento desta função (mais uma pergunta do LeetCode)

Question

Estou apenas tentando praticar o raciocínio por meio de grandes O de minhas soluções de leetcode.

Esta é a minha solução para um problema chamado " Plus One ". Estou simplesmente me perguntando qual é a hora do Big O aqui. Meus pensamentos e notas são acompanhados no código

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        def incrementer(digits,place):
            if (digits[-place] != 9):              # My base case
                digits[-place] = digits[-place] + 1
                return digits
            else:
                try:
                    next = digits[-place-1]
                except IndexError:
                    digits = [0]*(place+1) # This takes O(n) time?
                    digits[0] = 1
                    return digits
                digits[-place] = 0
                # Recursive case
                return incrementer(digits,place+1) # Recursive Case # O(n)?

        return incrementer(digits,1)

Acredito que isso resultará em O (n ^ 2) na pior das hipóteses, porque isso significaria que teria passado por toda a matriz e, em seguida, criado uma nova matriz de tamanho n + 1, preenchida com 0s. Estou correto neste pensamento? Isso ocorreria para um número como 9999999, onde todos os 9s acabam sendo invertidos e, em seguida, a nova matriz é criada para o novo local.

Answer 1

Você não está totalmente correto, mas perto; em Python, a criação de array é O (n) , e para alcançar essa linha no pior caso, você precisa percorrer toda a lista, que também é O (n). Então você tem O (n + n) que é O (2n) (mas nós descartamos os multiplicadores, então nós classificaríamos isso como O (n) novamente).

Mas, como disse Chepner, a iteração seria melhor aqui. E para sair de Ariel A, em vez do try exceptbloco para verificar se place + 1está fora dos limites do índice, você pode usar

if place + 1 >= len(digits)